**Next:** Problem 53: Minimum-Turn Cycle Cover in Planar Grid Graphs

**Previous:** Problem 51: Linear-Volume 3D Grid Drawings 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
- Status/Conjectures
Open.

- Partial and Related Results
[HLR92], [HR92]: Every outerplanar graph has queue-number \leq2.

[DW03b]: Every graph with bounded treewidth has bounded queue-number.

[Woo02]: Planar graphs have O(1) queue-number if and only if every n-vertex planar graph has a O(1) \times O(1) \times O(n) grid drawing.

[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
- Appearances
Above references.

- Categories
graph drawing

- Entry Revision History
D. Wood, 7 Dec. 2003.

- [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.