Planar graphs have bounded queue-number

Abstract

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 have strong connections to other topics, including the following two examples. First, they 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. Second, we give a simple proof of the result by DeVos et al. (2004) that graphs in a proper minor-closed class have low treewidth colourings.

References in corpus (12)

• Diameter and Treewidth in Minor-Closed Graph Families
• Layout of Graphs with Bounded Tree-Width
• An annotated bibliography on 1-planarity
• Layered Separators in Minor-Closed Graph Classes with Applications
• On Tree-Partition-Width
• Improper Colourings inspired by Hadwiger's Conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Track Layouts, Layered Path Decompositions, and Leveled Planarity
• Clique Minors in Cartesian Products of Graphs
• Upward Three-Dimensional Grid Drawings of Graphs
• Treewidth of Cartesian Products of Highly Connected Graphs
• Bad News for Chordal Partitions

Cited by in corpus (14)

• Adjacency Labelling for Planar Graphs (and Beyond)
• Sparse universal graphs for planarity
• Notes on Graph Product Structure Theory
• Packing Topological Minors Half-Integrally
• Improved bounds for weak coloring numbers
• Product structure of graphs with an excluded minor
• Colouring Strong Products
• Product structure extension of the Alon--Seymour--Thomas theorem
• Parameterizing Path Partitions
• Assouad-Nagata dimension of minor-closed metrics
• Nonrepetitive graph colouring
• The Excluded Tree Minor Theorem Revisited
• Neighborhood complexity of planar graphs
• The grid-minor theorem revisited