PaperlayerView exact revision on arXiv

Source-linked AI summary

Planar graphs have bounded queue-number

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood

arXiv:1904.04791v5cs.DMmath.CO

TL;DR

The paper addresses whether planar graphs have bounded queue-number, a conjecture posed in 1992. It introduces layered partitions and proves bounded queue-number for planar graphs, bounded-Euler-genus graphs, and every proper minor-closed class. The paper also connects layered partitions to strong products, minor-closed classes, and low-treewidth colourings.

  • Problem

    The paper addresses the open question of whether planar graphs have bounded queue-number, a conjecture posed by Heath, Leighton, and Rosenberg in 1992.

  • Method

    The paper introduces layered partitions, combining a vertex partition and layering with bounded layered width and a quotient graph of bounded treewidth.

  • Results

    The paper proves bounded queue-number for planar graphs, graphs of bounded Euler genus, and every proper minor-closed class.

  • Takeaways & Limitations

    Layered partitions provide a structural framework connecting queue layouts with strong-product representations and low-treewidth colourings.

  • Takeaways & Limitations

    The paper notes that significantly improving the planar upper bound appears to require new ideas; the best lower bound is 4.

Abstract

from arXiv · show

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.

1 Introduction

This paper proves the long-standing conjecture that planar graphs have bounded queue-number, obtaining an upper bound of 49. It extends the result to bounded-Euler-genus graphs and all proper minor-closed classes using layered partitions.

  • 1 Introduction: Queue layouts partition edges into queues under a vertex ordering, where each queue contains pairwise non-nested edges.Stack layouts instead use pairwise non-crossing edges.
  • 1 Introduction: The introduction situates the result after earlier bounds ranging from O(√n) to O(log n) and bounded-degree bounds of O(∆^2).
  • 1 Introduction: The paper proves that planar graphs have bounded queue-number, resolving a 27-year open conjecture.The best upper bound obtained is 49.
  • 1 Introduction: Graphs with Euler genus g have queue-number at most O(g), with an obtained upper bound of 4g +49.
  • 1 Introduction: Every proper minor-closed class of graphs has bounded queue-number.
  • 1 Introduction: The key structural tool is a layered partition: a vertex partition and graph layering with bounded per-layer part size and a bounded-treewidth quotient.These partitions support the queue-number results and have applications beyond queue layouts.

2 Tools

The paper develops layered partitions: partitions whose parts are small within each graph layer and whose quotient has bounded treewidth. These structures connect queue-number, layered treewidth, and graph decompositions.

  • 2.1 Layerings: A layering is an ordered vertex partition in which every edge joins vertices in the same or consecutive layers.
  • 2.2 Treewidth and Layered Treewidth: Treewidth is the minimum width of a tree-decomposition, measuring how closely a graph resembles a tree.
  • 2.2 Treewidth and Layered Treewidth: Layered treewidth bounds the number of vertices from each graph layer that may appear in any tree-decomposition bag.
  • 2.3 Partitions and Layered Partitions: A partition divides vertices into parts, with the quotient joining two parts whenever an original edge connects them.
  • 2.3 Partitions and Layered Partitions: A layered partition requires each part to contain at most ℓ vertices in every layer.
  • 2.3 Partitions and Layered Partitions: If the quotient has treewidth at most k and layered width is at most ℓ, the graph has layered treewidth at most (k + 1)ℓ.
  • 2.3 Partitions and Layered Partitions: Bounded layered partitions yield O(1) queue-number bounds, improving on the O(log n) bounds known from bounded layered treewidth.

3 Queue Layouts via Layered Partitions

The queue-layout argument orders vertices layer by layer and expands a queue layout of the quotient graph across bounded-size bags. Splitting edges by layer and bag relation yields a bounded number of queues.

  • 3 Queue Layouts via Layered Partitions: A graph with layered width ℓ over a quotient having a k-queue layout receives a bounded queue layout through a layer-by-layer vertex ordering.
  • 3 Queue Layouts via Layered Partitions: Replacing each quotient vertex by a block of at most ℓ vertices preserves a queue layout using ℓ queues.
  • 3 Queue Layouts via Layered Partitions: The construction separates intra-level intra-bag, intra-level inter-bag, inter-level intra-bag, and inter-level inter-bag edges into distinct queue families.
  • 3 Queue Layouts via Layered Partitions: The resulting bound is 3ℓ(2k −1) + [truncated in the supplied passage] when the quotient has treewidth at most k.

4 Proof of Theorem 1: Planar Graphs

The proof introduces vertical-path partitions whose quotients have bounded treewidth, then converts these layered partitions into a bounded queue layout for every planar graph.

  • 4 Proof of Theorem 1: Planar Graphs: Planar graphs admit a partition of layered width 1, valid for every BFS layering, whose quotient has treewidth at most 8.The partition consists of connected vertical paths, so each part meets each BFS layer at most once.
  • 4 Proof of Theorem 1: Planar Graphs: Vertical paths in a rooted spanning tree yield a partition of any connected planar graph whose quotient has treewidth at most 8.Every vertical path in a BFS spanning tree is a geodesic, strengthening the cited geodesic-partition result.
  • 4 Proof of Theorem 1: Planar Graphs: Theorem 12 is proved by inductively partitioning near-triangulations into vertical paths while maintaining a bounded-width tree-decomposition of the quotient.The induction uses a Sperner-triangle construction and recursively formed subgraphs bounded by vertical paths.
  • 4 Proof of Theorem 1: Planar Graphs: The inductive construction colours boundary paths, applies Sperner’s Lemma to find a tricoloured internal face, and uses its tree paths to split the instance.The resulting paths and cycles support the recursive decomposition while preserving verticality.
  • 4.1 Reducing the Bound: The layered-partition theorem and queue-layout lemmas prove that planar graphs have bounded queue-number, with an explicit upper bound of 49 in the improved construction.Theorem 15 supplies layered width 3 and a planar quotient of treewidth at most 3; the associated queue-layout lemma gives 49 queues.

5 Proof of Theorem 2: Bounded-Genus Graphs

For bounded-Euler-genus graphs, the proof removes a sparse connected subgraph to expose a planar remainder, then transfers planar layered partitions back to the original graph.

  • 5 Proof of Theorem 2: Bounded-Genus Graphs: Graphs of Euler genus g therefore have bounded queue-number, with a direct bound linear in g.The paper also notes that the product of layered width and quotient-treewidth parameters must be Ω(g), so the partition trade-off is asymptotically constrained.
  • 5 Proof of Theorem 2: Bounded-Genus Graphs: A connected subgraph Z can be chosen with at most 2g vertices per BFS layer so that deleting Z leaves a planar graph.The construction also preserves the original layering outside Z through a connected planar supergraph and compatible BFS tree.
  • 5 Proof of Theorem 2: Bounded-Genus Graphs: The proof cuts edges of Z at incident vertices, producing a connected planar graph in which the split vertices lie on one face.Euler’s formula shows that the cut surface has genus zero and exactly one newly created face.
  • 5 Proof of Theorem 2: Bounded-Genus Graphs: The planarized graph is augmented and contracted so that a planar quotient partition transfers back, producing an apex quotient of treewidth at most 9.The transferred partition is connected because its parts outside Z are vertical paths and Z itself is connected.
  • 5 Proof of Theorem 2: Bounded-Genus Graphs: Every graph of Euler genus g has a partition of layered width at most max{2g, 3}, valid for every BFS layering, whose quotient is apex with treewidth at most 4.This is the stronger non-connected-partition formulation; a connected alternative has layered width at most max{2g,1} and quotient treewidth at most 9.

6 Proof of Theorem 3: Excluded Minors

The proof combines the graph minor structure theorem with layered partitions to establish bounded queue-number for every proper minor-closed class. It also characterizes when minor-closed classes admit such partitions through excluded apex graphs.

  • Excluded-minor structure: Every proper minor-closed class consists of clique-sums of k-almost-embeddable graphs for some class-dependent constant k.The decomposition uses graphs on surfaces, vortices, apex vertices, and clique-sums.
  • Excluded-minor structure: Every proper minor-closed class has bounded queue-number, obtained as an immediate corollary of the almost-embeddable and clique-sum lemmas.The proof uses the Robertson–Seymour structure theorem to reduce graphs in the class to clique-sums of almost-embeddable graphs.
  • Layered partitions: A strongly (g, p, k, a)-almost-embeddable graph has a connected partition of layered width at most max{2g + 4p −4, 1}, whose quotient has treewidth at most 11k + a + 10.This extends the no-apex construction by incorporating apex vertices into the quotient-treewidth bound.
  • Characterisation: For minor-closed classes, bounded layered partitions, bounded layered treewidth, bounded local treewidth, and exclusion of an apex graph are equivalent conditions.The characterization also includes clique-sum decompositions into strongly k-almost-embeddable graphs.
  • Characterisation: The minor-closed assumption is essential: the n × n × n grid has bounded local treewidth but layered treewidth Ω(n).For this grid, any partition with layered width ℓ and quotient treewidth k must satisfy kℓ ⩾ Ω(n).

7 Strong Products

Layered partitions yield strong-product representations of planar, bounded-genus, almost-embeddable, and proper minor-closed graphs. These representations place each graph class inside products involving a path and a bounded-treewidth graph.

  • Product interpretation: A graph has an H-partition of layered width at most ℓ exactly when it is a subgraph of H ⊠P ⊠Kℓ for some path P.This observation translates layered partitions directly into strong-product containment.
  • Planar graphs: Every planar graph is a subgraph of H ⊠P, where H is planar with treewidth at most 8 and P is a path.A second representation uses H ⊠P ⊠K3 with H of treewidth at most 3.
  • Bounded Euler genus: Every graph of Euler genus g is a subgraph of H ⊠P ⊠Kmax{2g,1}, with H an apex graph of treewidth at most 9.Alternative representations use treewidth at most 4 or a planar graph of treewidth at most 8 joined with K2g.
  • Almost-embeddable graphs: Every k-almost-embeddable graph is a subgraph of (H ⊠P ⊠K6k) + Kk, with H of treewidth at most 11k + 10.Another representation uses ((H + K(6k)(k+1)) ⊠P) + Kk with H of treewidth at most 9k + 8.
  • Minor-free graphs: For every apex graph X, every X-minor-free graph is a subgraph of H ⊠P for some H of bounded treewidth and some path P.This follows from the layered-partition characterization and the strong-product equivalence.
  • Minor-closed classes: For every proper minor-closed class, each graph is a clique-sum of pieces contained in H_i ⊠P_i, with each H_i having bounded treewidth.The bounds depend only on the class, while the paths and auxiliary graphs vary across pieces.
  • Universal graphs: Strong products provide structured universal graphs: T8 ⊠Q contains every finite planar graph.Here T8 has treewidth 8 and Q is the infinite path.

8 Non-Minor-Closed Classes

The paper extends bounded queue-number results from planar and bounded-genus graphs to several non-minor-closed classes, including crossing, map, and string graphs.

  • Expansion lemma: A graph formed by short paths through vertices of degree at most ∆ from a k-queue graph has queue-number below 2(2k(∆ + 1))^(c+1).Edges are grouped by path length and classified using queue labels, orientations, and an edge-colouring with ∆ + 1 colours.
  • (g, k)-planar graphs: Every (g, k)-planar graph has queue-number at most 2(40g + 490)^(k+2).The proof replaces crossings by degree-4 vertices and applies the bounded-path expansion lemma.
  • Map graphs: Every (g, d)-map graph has bounded queue-number via its half-square representation and a bounded-degree path expansion.The supplied proposition states the bound but its displayed numerical expression is incomplete.
  • String graphs: Every (g, k)-string graph has queue-number at most 2(40g + 490)^(2k+1).The construction subdivides curve intersections and endpoints to obtain an embedded graph before applying the expansion lemma.

9 Applications and Connections

Layered partitions connect queue-number results to low-treewidth colourings, track layouts, and three-dimensional grid drawings.

  • Low Treewidth Colourings: The layered-partition approach yields tree-decompositions of width at most 66k(k + 1)(2c − 1) + k − 1 for the relevant subgraphs.The construction combines decompositions across layers and uses a bounded-treewidth quotient graph.
  • Low Treewidth Colourings: Every proper minor-closed class admits edge or vertex c-colourings such that the union of any c − 1 colour classes has bounded treewidth.The theorem holds for every fixed c ≥ 2.
  • Track Layouts: Every proper minor-closed class has bounded track-number, including planar graphs with track-number at most 5(2 · 49)^4 = 461,184,080.Queue-number and track-number are tied through converse bounding functions.
  • Three-Dimensional Grid Drawings: Every planar graph with n vertices has a 3-dimensional grid drawing with O(n) volume.The result follows from bounded track layouts and the conversion from track layouts to grid drawings.
  • Three-Dimensional Grid Drawings: Graphs of Euler genus g have 3-dimensional grid drawings with gO(g^(4/7))n volume.The same framework also gives this genus-dependent bound.

10 Open Problems

The paper leaves open questions about sharper queue-number bounds, broader graph classes, converse relations with stack-number, and algorithmic uses of layered structure.

  • Queue-number bounds: The maximum queue-number of planar graphs is unknown: the paper gives an upper bound of 48, while the best lower bound is 4.The authors state that significant improvement of the upper bound seems to require new ideas.
  • Stack-number and queue-number: The converse relationship between queue-number and stack-number remains open in general, although this paper resolves the first open case because 2-stack graphs are planar.The open direction asks whether qn(G) can be bounded as a function of sn(G).
  • Broader classes: It remains open whether graphs with strongly sub-linear separators have bounded queue-number.The proposed class is closed under subgraphs and is motivated as a possible larger setting for bounded queue-number.
  • Treewidth: It remains open whether treewidth k implies queue-number bounded by a polynomial function of k.The stated best lower and upper bounds for the function are k + 1 and 2k − 1.
  • Algorithmic applications: The authors ask whether the results have algorithmic applications, including more precise layered decompositions for Baker-style approximation schemes.They also state that their decomposition and queue-layout proofs yield polynomial-time algorithms.

Note Added in Proof

Subsequent work developed analogues, algorithms, and improvements related to the paper’s product-structure, decomposition, and track-number results.

  • Follow-up work: Follow-up work extended related product-structure results to bounded-degree minor-closed graphs, k-planar graphs, and other non-minor-closed classes.The paper points to a survey on product structure theorems.
  • Follow-up work: Morin presented O(n log n)-time algorithms for finding the partitions in Theorems 11 and 15.This gives an explicit algorithmic improvement for computing the decompositions.
  • Follow-up work: Pupyrev improved the planar track-number bound from Theorem 53.The supplied passage notes the improvement without giving its resulting bound.
Loading 1904.04791v5…