Name
Abstract | ||
|---|---|---|
A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg states that the queue number of planar graphs is bounded.This conjecture has been partially settled in the positive for several sub- families of planar graphs (most of which have bounded treewidth).
In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree as bounded queue number.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3313276.3316324 | Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |
Keywords | DocType | Volume |
Queue number, graph algorithms, planar graphs | Journal | 48 |
Issue | ISSN | ISBN |
5 | 0737-8017 | 978-1-4503-6705-9 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Bekos | 1 | 250 | 38.21 |
| Henry Förster | 2 | 3 | 4.40 |
| Martin Gronemann | 3 | 26 | 7.96 |
| Tamara Mchedlidze | 4 | 136 | 25.56 |
| Fabrizio Montecchiani | 5 | 261 | 37.42 |
| Chrysanthi N. Raftopoulou | 6 | 32 | 8.53 |
| torsten ueckerdt | 7 | 141 | 26.26 |