Planar Graphs have Bounded Queue-Number

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

Authors

• Vida Dujmovic
• Gwenaël Joret
• Piotr Micek
• Pat Morin
• Torsten Ueckerdt
• David R. Wood

Keywords

• Layout
• Queueing analysis
• Heating systems
• Computer science
• Tools
• Data structures
• Mathematics
• Planar Graphs
• Layering
• Small Class
• Class Of Graphs
• Proof Of Theorem
• Geodesic
• Linear Order
• Functional Graph
• Graph Partitioning
• Graph Layout
• Internal Face
• Vertical Path
• graph theory
• queue layout
• queue-number
• planar graph
• treewidth
• layered partition
• strong product
• Euler genus
• graph minor
• graph drawing