Next: Problem 53: MinimumTurn Cycle
Up: The Open Problems Project
Previous: Problem 51: LinearVolume 3D
Problem 52: QueueNumber of Planar Graphs
 Statement
 Does every planar graph have O(1) queuenumber? A
queue layout of a graph consists of a linear order of the
vertices and a partition of the edges into nonnested queues.
Edge xy is nested inside edge vw if
v < x < y < w in the linear order. The queuenumber 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
 [HLR92,HR92]: Every tree has queuenumber ≤1.
 [HLR92,HR92]: Every outerplanar graph has
queuenumber ≤2.
 [DW03b]: Every graph with bounded treewidth has bounded
queuenumber.
 [Woo02]: Planar graphs have O(1) queuenumber if and
only if every nvertex planar graph has a
O(1)×O(1)×O(n) grid drawing.
 [DW03a]: Planar graphs have O(1) queuenumber 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.
 DW03a

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

Vida Dujmović and David R. Wood.
Treepartitions of ktrees 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 205217. SpringerVerlag, 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):398412, 1992.
 HR92

Lenwood S. Heath and Arnold L. Rosenberg.
Laying out graphs using queues.
SIAM J. Comput., 21(5):927958, 1992.
 Woo02

David R. Wood.
Queue layouts, treewidth, and threedimensional
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 348359.
Springer, 2002.
Next: Problem 53: MinimumTurn Cycle
Up: The Open Problems Project
Previous: Problem 51: LinearVolume 3D
The Open Problems Project  September 19, 2017