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 $\leq$ 1.
2. [HLR92,HR92]: Every outerplanar graph has queue-number $\leq$ 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.