Planar graphs have bounded queue-number

Vida Dujmovic, Gwenael Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

14 Citations (Scopus)

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 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.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
Subtitle of host publication60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019; Baltimore; United States; 9 November 2019 through 12 November 2019
Place of PublicationPiscataway NJ USA
PublisherIEEE Computer Society
Pages862-875
Number of pages14
ISBN (Electronic)9781728149523, 9781728149530
DOIs
Publication statusPublished - 6 Jan 2020
EventIEEE Annual Symposium on Foundations of Computer Science, 2019 - Baltimore, United States of America
Duration: 9 Nov 201912 Nov 2019
Conference number: 60th

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE
Volume2019-November
ISSN (Print)0272-5428
ISSN (Electronic)2575-8454

Conference

ConferenceIEEE Annual Symposium on Foundations of Computer Science, 2019
Abbreviated titleFOCS 2019
CountryUnited States of America
CityBaltimore
Period9/11/1912/11/19

Keywords

  • Euler genus
  • Graph drawing
  • Graph minor
  • Graph theory
  • Layered partition
  • Planar graph
  • Queue layout
  • Queue-number
  • Strong product
  • Treewidth

Cite this