Name
Abstract | ||
|---|---|---|
In this paper, we show that any $B_2$-VPG graph (i.e., an intersection graph of orthogonal curves with at most 2 bends) can be decomposed into $O(\log n)$ outerstring graphs or $O(\log^3 n)$ permutation graphs. This leads to better approximation algorithms for hereditary graph problems, such as independent set, clique and clique cover, on $B_2$-VPG graphs. |
Year | Venue | DocType |
|---|---|---|
2016 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1612.07276 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Derka | 1 | 0 | 1.01 |
| Therese Biedl | 2 | 902 | 106.36 |