Next: Problem 53: Minimum-Turn Cycle Cover in Planar Grid Graphs
Previous: Problem 51: Linear-Volume 3D Grid Drawings of Planar Graphs
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).
Open.
[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).
Above references.
graph drawing
D. Wood, 7 Dec. 2003.
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.
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.
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.
Lenwood S. Heath and Arnold L. Rosenberg. Laying out graphs using queues. SIAM J. Comput., 21(5):927–958, 1992.
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.