Planar Graphs Have Bounded Queue-Number
Top Cited Papers
- 6 August 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (4), 1-38
- https://doi.org/10.1145/3385731
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.Keywords
Funding Information
- Polish National Science Center
- Australian Research Council
- Natural Sciences and Engineering Research Council of Canada
- Wallonia-Brussels Federation
This publication has 80 references indexed in Scilit:
- Treewidth of Cartesian Products of Highly Connected GraphsJournal of Graph Theory, 2012
- Queue layouts of iterated line directed graphsDiscrete Applied Mathematics, 2007
- Decidability of string graphsJournal of Computer and System Sciences, 2004
- Recognizing string graphs in NPJournal of Computer and System Sciences, 2003
- Approximation Algorithms for Independent Sets in Map GraphsJournal of Algorithms, 2001
- Diameter and Treewidth in Minor-Closed Graph FamiliesAlgorithmica, 2000
- Domino TreewidthJournal of Algorithms, 1997
- Genus g Graphs Have Pagenumber O(√g)Journal of Algorithms, 1994
- Embedding planar graphs in four pagesJournal of Computer and System Sciences, 1989
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986