Bounded queue number of planar graphs

Queue Number of Planar Graphs · arXiv:1507.01120

arXiv Problem medium confidence— first stated 2017-01-09

Authors: Gwenaël Joret, Piotr Micek, Veit Wiechert

Status solved high confidence

The conjecture that planar graphs have bounded (constant) queue number was resolved affirmatively by Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood in a 2019 arXiv preprint (published in J. ACM 2020), proving that every planar graph has queue number at most 49. The proof introduces layered partitions as a key structural tool and also shows that every proper minor-closed class of graphs has bounded queue number. Notably, Joret and Micek, two of the three authors of the source paper 1507.01120, are among the co-authors of the solving paper.

Cited literature (1)

proof Planar graphs have bounded queue-number (2020)

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood · Journal of the ACM · arXiv:1904.04791 · doi:10.1145/3385731

Proves that planar graphs have bounded queue number (at most 49), resolving the long-standing conjecture of Heath, Leighton, and Rosenberg from 1992 and cited as open in the source paper.

Reviewer notes. The conjecture is fully resolved. The solving paper arXiv:1904.04791 (J. ACM 67(4):22, 2020) was verified via WebFetch of https://arxiv.org/abs/1904.04791. Two of the three authors of the source paper (Joret and Micek) are co-authors of the solving paper.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. A challenging open problem in the area of queue layouts is to decide whether planar graphs have constant queue number.

Context

Mentioned in the applications section where the authors note that graphs with bounded queue number form a class with bounded expansion (Dujmović and Wood), so Theorem 1 implies that posets whose cover graphs have bounded queue number have dimension bounded by a function of the queue number and the height. The queue-number problem for planar graphs is cited as independently interesting.

Notes. This is an existing open problem from the queue-layout literature, referenced via citation [3]; it is not introduced by the paper's authors but is presented in running prose as background motivation. No labelled theorem environment. PDF source — math notation appears clean for this item.

Source paper

Sparsity and dimension
Gwenaël Joret, Piotr Micek, Veit Wiechert · 2017-01-09
https://arxiv.org/abs/1507.01120 PDF source