next up previous
Next: Problem 53: Minimum-Turn Cycle Up: The Open Problems Project Previous: Problem 51: Linear-Volume 3D


Problem 52: Queue-Number of Planar Graphs

Statement
Does every planar graph have O(1) queue-number? A queue layout of a graph consists of a linear order of the vertices and a partition of the edges into non-nested queues. Edge xy is nested inside edge vw if v < x < y < w in the linear order. The queue-number of a graph G is the minimum number of queues in a queue layout of G. This question amounts to asking whether every planar graph has a vertex ordering with a constant number of pairwise nested edges (called a rainbow).
Origin
Heath, Leighton, and Rosenberg [HLR92,HR92].
Status/Conjectures
Open.
Partial and Related Results
  1. [HLR92,HR92]: Every tree has queue-number ≤1.
  2. [HLR92,HR92]: Every outerplanar graph has queue-number ≤2.
  3. [DW03b]: Every graph with bounded treewidth has bounded queue-number.
  4. [Woo02]: Planar graphs have O(1) queue-number if and only if every n-vertex planar graph has a O(1)×O(1)×O(n) grid drawing.
  5. [DW03a]: Planar graphs have O(1) queue-number if and only if Hamiltonian bipartite planar graphs have O(1) bipartite thickness. The bipartite thickness of a bipartite graph G is the minimum k such that G can be drawn with the vertices on each side of the bipartition along a line, with the two lines parallel, and with each edge assigned to one of k ``layers'' so that no two edges in the same layer cross (when drawn as straight line segments).
Related Open Problems
Problem 51.
Appearances
Above references.
Categories
graph drawing
Entry Revision History
D. Wood, 7 Dec. 2003.

Bibliography

DW03a
Vida Dujmović and David R. Wood.
Stacks, queues and tracks: Layouts of graphs subdivisions.
Technical Report TR-2003-07, School of Computer Science, Carleton University, Ottawa, Canada, 2003.

DW03b
Vida Dujmović and David R. Wood.
Tree-partitions of k-trees with applications in graph layout.
In Hans Bodlaender, editor, Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science (WG'03), volume 2880 of Lecture Notes in Comput. Sci., pages 205-217. Springer-Verlag, 2003.

HLR92
Lenwood S. Heath, Frank Thomson Leighton, and Arnold L. Rosenberg.
Comparing queues and stacks as mechanisms for laying out graphs.
SIAM J. Discrete Math., 5(3):398-412, 1992.

HR92
Lenwood S. Heath and Arnold L. Rosenberg.
Laying out graphs using queues.
SIAM J. Comput., 21(5):927-958, 1992.

Woo02
David R. Wood.
Queue layouts, tree-width, and three-dimensional graph drawing.
In Manindra Agrawal and Anil Seth, editors, Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FST TCS '02), volume 2556 of Lecture Notes in Comput. Sci., pages 348-359. Springer, 2002.


next up previous
Next: Problem 53: Minimum-Turn Cycle Up: The Open Problems Project Previous: Problem 51: Linear-Volume 3D
The Open Problems Project - December 04, 2015