A Gap in the 42-Queue Layout Algorithm for Planar Graphs

Sergey Pupyrev

REVIEW 3 major objections 3 minor 20 references

A Gap in the 42-Queue Layout Algorithm for Planar Graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that the published proof of the 42-queue upper bound for planar graphs has a gap: a 19-vertex instance shows that the required missed-path property of a next-level component can fail, so the bound is not established.

desk verdict A short, credible note that identifies a real gap in BGR's 42-queue proof; the 19-vertex counterexample is well targeted and the paper honestly limits its claim to invalidating the published argument, not lowering the bound. read the letter →

arxiv 2608.05508 v1 pith:WXMJ7MJQ submitted 2026-08-06 cs.DM math.CO

Sergey Pupyrev This is my paper · ORCID

classification cs.DMmath.CO MSC 05C1005C8568R10

keywords queuelayoutnumberplanargraphstripoddecompositionproductstructure3-treesproofgapcounterexample

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This note tries to establish that the recent proof of a 42-queue upper bound for planar graphs, due to Bekos, Gronemann, and Raftopoulou, contains a genuine gap. It exhibits a concrete plane triangulation with 19 vertices and a valid execution of the algorithm in which a next-level component's tripod-vertices touch all three vertical paths of the parent tripod, contradicting a claim the proof relies on. Consequently, the published argument does not prove the 42-queue bound; the product-structure approach only yields a 48-queue bound. The author also sketches two possible repair directions, but does not establish either one.

What carries the argument

The key object is the tripod reordering step of BGR, which orders the three vertical paths of each tripod so that a suitable next-level component misses the first path. The counterexample centers on the component c = {τ6, τ7, d}, formed after subdividing a parallel edge between τ3 and τ4 with an auxiliary vertex d and adding edges (τ6, d) and (τ7, d) to complete the partial 3-tree H0 to a maximal planar 3-tree H′. The peeling levels are L0 = {τ0, τ1, τ2}, L1 = {τ3, τ4, τ5}, and L2 = {τ6, τ7, d}; c is the L2-neighborhood of τ4, and the 5-queue layout of planar 3-trees assigns edges between τ4 and c to one of the binding queues Q2 or Q3.

What would settle it

Reproduce the BGR construction on the 19-vertex graph of Figure 2(a) with the tripod decomposition of Figure 2(b), and test every valid choice of subdivision and base edge. If every resulting next-level component of L2 adjacent to τ4 has tripod-vertices that miss some vertical path of τ4, then Claim 2 survives for this instance and the gap could be evadable.

Watch

Extended reading notes

Core claim

The central discovery is that Claim 2 in the BGR algorithm is false in general. For the 19-vertex triangulation G shown in Figure 2, the next-level component c = {τ6, τ7, d} adjacent to τ4 has tripod-vertices T(c) = V(τ6) ∪ V(τ7). Since V(τ6) misses $p^{1}$_4 and V(τ7) misses $p^{2}$_4, their union touches all three vertical paths $p^{1}$_4, $p^{2}$_4, $p^{3}$_4, so T(c) misses no vertical path of τ4. This contradicts Claim 2, which Lemma 6 applies to every Q2- and Q3-component, including c. The underlying cause is that augmenting H0 to a maximal planar 3-tree can merge tripods from different recursive regions, and the missed paths supplied by each region need not coincide.

Load-bearing premise

The counterexample assumes that BGR's algorithm permits the specific execution: the parallel edge between τ3 and τ4 can be subdivided as shown, the base-edge choice makes c a Q2- or Q3-component, and the geometric fact from Figure 2 that τ6 misses $p^{1}$_4 while τ7 misses $p^{2}$_4 is correct.

Editorial extensions

If this is right

The published proof does not establish the 42-queue upper bound for planar graphs.
The best bound validated by the product-structure approach remains 48 queues, since the separate one-queue saving for intra-bag inter-layer edges is still valid.
The tripod reordering step of BGR cannot be applied as stated to arbitrary tripod decompositions.
Repairing the proof requires either a region-preserving augmentation of partial planar 3-trees or a 5-queue layout for embedded multigraphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The gap suggests that any argument relying on local missed-path properties must keep next-level components within a single recursive region; otherwise the missed paths from different regions can cancel out, leaving no missed path.
The counterexample may indicate that other queue-layout algorithms using arbitrary augmentation of partial 3-trees face similar obstructions when merging topological sectors.
A testable next step is to determine whether a constrained, region-preserving augmentation can recover the 6-queue saving, potentially yielding a bound between 42 and 48, or whether the true queue number of planar graphs is closer to the lower bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this note does what it says. It points to a specific load-bearing claim in BGR's 42-queue paper, gives a 19-vertex plane triangulation where that claim fails, and explains why the failure happens: the drawing-preserving augmentation can merge tripods from different recursive regions into one next-level component, so each tripod misses a different vertical path and the union touches all three. That mechanism is new as far as I know, and it is a clean way to refute the published proof without having to produce a lower bound above 42. The note also correctly rescues the separate one-queue saving for intra-bag inter-layer edges, leaving 48 queues from the product-structure route. Credit where due: the paper is well-scoped, carefully states what it does and does not show, and the explicit elimination order certifying that H' is a maximal planar 3-tree is a nice concrete touch.

The main soft spot is the one the stress-test note flagged: the counterexample depends on BGR leaving certain choices open—which parallel edge is subdivided, how the augmentation is completed, and which queue the component c receives in the 5-queue layout. The note asserts BGR does not prescribe these choices but does not re-derive BGR's full rules. I checked the relevant passage: the note is explicit about this assumption and invites the reader to verify. For a note of this kind, that is acceptable, especially since the author is clearly an expert in the area. The geometry is presented through a figure rather than a coordinate list, but the text describes which paths are touched and missed, and the figure is clear enough for a specialist to verify. These are minor concerns, not load-bearing flaws.

The stress-test worry that the gap could "evaporate" if BGR's augmentation is canonical is not supported by the paper under review. The note's whole point is that the published proof relies on a generic drawing-preserving augmentation [3,15] and does not enforce region-preservation. Unless the BGR paper secretly has such a rule, the counterexample executes legally. I did not see evidence of such a rule in the note's summary, and the author is in a position to know.

Who benefits: anyone working on queue layouts, graph product structure, or planar graph linear layouts. The note is a useful correction to the literature and would prevent future papers from citing the 42 bound as established. It deserves a serious referee—not because it is earth-shattering, but because correcting a published upper bound is important for the community and the argument is sound. I would send it to peer review and expect it to be accepted after possibly adding a bit more detail about the execution choices.

Recommendation: engage with it; it is a legitimate, well-executed critique.

Referee Report

3 major / 3 minor

Summary. The note argues that the proof of the 42-queue upper bound for planar graphs by Bekos, Gronemann, and Raftopoulou (BGR) contains a gap. It isolates an implicit claim, called Claim 2, that every next-level component's tripod-vertices miss a vertical path of the parent tripod, and constructs a 19-vertex plane triangulation with a tripod decomposition in which a next-level component c = {τ6, τ7, d} has tripod-vertices touching all three vertical paths of τ4. The note concludes that Claim 2 is false, that the proof of Lemma 6 in BGR therefore does not go through, and that the surviving bound from this approach is 48 queues.

Significance. If the counterexample is valid, the note correctly identifies a serious gap in a published proof, restoring 48 as the best queue-number bound obtained via the product-structure route. The argument is logically clear and carefully limited: it does not assert that planar graphs have queue number greater than 42, only that BGR's proof is incomplete. The note is honest about the surviving 48-queue bound and suggests two plausible repair directions. However, the validity of the counterexample rests on the legality of the specific H′ construction and on the claim that c can be a Q2/Q3-component; these points are asserted rather than fully demonstrated, which weakens the note in its current form.

major comments (3)

[§3.1, Figure 2(c)] The counterexample relies on the assertion that BGR's augmentation step leaves open which parallel edge between τ3 and τ4 is subdivided and that adding the edges (τ6,d) and (τ7,d) yields a valid maximal planar 3-tree H′. The note says BGR 'does not prescribe' these choices, but it does not reproduce the exact augmentation rule from [4] or show that the displayed H′ is a legal output of that rule. If BGR's augmentation is canonical and always separates τ6 and τ7, then the instance is not a valid execution. Please provide the precise rules from [4] and prove that the displayed H′ (or some H′ with the same component c) is among the legal outputs.
[§3.1, last paragraph] The claim that 'there are valid executions in which c is one of the Q2-components or one of the Q3-components' is essential, because Claim 2 is applied in BGR only to Q2/Q3-components. The note does not exhibit a 5-queue layout of H′ or prove that some legal base-edge choice assigns the edges from τ4 to c to Q2 or Q3. Without this, the gap may be evadable by choosing a base edge that assigns c to Q4. Please supply the explicit 5-queue layout or a rigorous argument that such a choice exists.
[§3.1, Figure 2(b)] The geometric facts that V(τ6) misses p1_4 and V(τ7) misses p2_4 are stated from the figure, but no coordinate list or formal description of the tripod decomposition is given. Since these facts are load-bearing for the contradiction to Claim 2, the note should make the instance machine-checkable (for example, by providing vertex coordinates, the BFS tree, and the tripod recursion in a table).

minor comments (3)

[§3.2] The sentence 'The 6-queue saving for inter-bag edges proved in Lemma 6 is not established by the published proof' could be clearer if it distinguished the two savings mentioned in the abstract; the 1-queue saving for intra-bag inter-layer edges is retained.
[§2, paragraph on Claim 1] The definition of the paths p1_i, p2_i, p3_i in the sentence beginning 'For i = 1,2,3' is dense; a short reference to Figure 1(b) would help the reader.
[Abstract] The phrase 'one of the choices required by the algorithm is not guaranteed to exist' could be made more precise by naming the choice (the first vertical path in the tripod reordering) already in the abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the note is a self-contained counterexample critique of BGR, not a derivation from its own conclusion.

full rationale

This note is a self-contained critique of BGR, not an attempted derivation from the target theorem. The central claim is that Claim 2 is false in a concrete instance: the union T(c)=V(τ6)∪V(τ7) touches p1_4, p2_4 and p3_4 while missing no vertical path, since the auxiliary vertex d contributes no vertices. This is an external counterexample argument, not a reduction of a prediction to a fitted input. The only self-citations are used to describe the standard 5-queue layout and queue-layout background; they are not used to justify the gap. The reviewer's concern that BGR might secretly fix the base-edge or augmentation choices is a correctness/admissibility caveat, not evidence of circularity. Accordingly there is no circular step and the score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The note's argument uses established background results (Sperner-based tripod recursion, rainbow/queue characterization, and 5-queue layouts of planar 3-trees) plus the unformalized 19-vertex geometric instance. No fitted parameters or ad hoc entities are introduced; the auxiliary vertex d belongs to the BGR augmentation being refuted.

assumptions (5)

standard math Sperner's lemma guarantees the tripod recursion of DJMMUW produces a new tripod in every recursive region.
Invoked in Section 2 to define the recursive tripod decomposition and to construct the counterexample's hierarchy.
standard math The rainbow characterization is correct: a graph can be partitioned into k queues iff its linear order has no rainbow of size k+1.
Quoted in Section 1 as background; the note does not re-prove it.
domain assumption The 5-queue layout of maximal planar 3-trees from Alam et al. has the peeling-level structure with Q2 and Q3 components described.
Needed to make sense of BGR's tripod reordering and the note's claim that component c can be a Q2- or Q3-component.
domain assumption The 19-vertex triangulation and its tripod decomposition satisfy the stated miss/touch relations, with τ6 missing p1_4 and τ7 missing p2_4.
The core counterexample is read from Figure 2 and the recursion description; no independent machine-checked certificate is given.
domain assumption The augmented graph H' is a maximal planar 3-tree with the stated elimination order and peeling levels L0, L1, and L2.
This determines that τ6, τ7, and the auxiliary vertex d form one next-level component c adjacent to τ4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Gap in the 42-Queue Layout Algorithm for Planar Graphs." pith.science (2026). https://pith.science/paper/WXMJ7MJQ

@misc{pith2026260805508,
  author       = {Pith},
  title        = {Pith review of: A Gap in the 42-Queue Layout Algorithm for Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WXMJ7MJQ}},
  note         = {Machine review of arXiv:2608.05508}
}

abstract

A queue layout of a graph consists of a linear order of the vertices and a partition of the edges into queues so that no two edges in a single queue are nested. The minimum number of queues needed in a queue layout of a graph is called its queue number. The planar product structure theorem states that every planar graph is a subgraph of the strong product of a graph of simple treewidth at most $3$, a clique $K_3$, and a path. Such a strong product admits a queue layout with $49$ queues (Wood, 2005), which implies that the queue number of planar graphs is at most $49$. Recently, Bekos, Gronemann, and Raftopoulou (Algorithmica, 2023) investigated how the general approach based on the product structure can be optimized for planar graphs. They claim that by appropriately reordering the three vertices in each bag arising from a tripod, it is possible to reduce the queue number of planar graphs to~$42$. In this note we highlight a gap in their queue layout algorithm: one of the choices required by the algorithm is not guaranteed to exist. Hence the claimed upper bound of $42$ queues is not established by the published proof.

Figures

Figures reproduced from arXiv: 2608.05508 by the authors.

**Figure 2.** The counterexample. (a) The plane triangulation [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[4]

M. A. Bekos, M. Gronemann, and C. Raftopoulou. An improved upper bound on the queue number of planar graphs.Algorithmica, 85(2):544–562, 2023. 6

work page 2023
[1]

J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees.Algorithmica, 82(9):2564–2585, 2020

work page 2020
[2]

J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. The mixed page number of graphs.Theor. Comput. Sci., 931:131–141, 2022

work page 2022
[3]

Arnborg and A

S. Arnborg and A. Proskurowski. Characterization and recognition of partial 3-trees. SIAM Journal on Algebraic Discrete Methods, 7(2):305–314, 1986

work page 1986
[5]

Di Battista, F

G. Di Battista, F. Frati, and J. Pach. On the queue number of planar graphs.SIAM Journal on Computing, 42(6):2243–2285, 2013

work page 2013
[6]

Dujmovi´c

V. Dujmovi´c. Graph layouts via layered separators.Journal of Combinatorial Theory, Series B, 110:79–89, 2015

work page 2015
[7]

Dujmovi´c and F

V. Dujmovi´c and F. Frati. Stack and queue layouts via layered separators.J. Graph Algorithms Appl., 22(1):89–99, 2018

work page 2018
[8]

Dujmovi´c, G

V. Dujmovi´c, G. Joret, P . Micek, P . Morin, T. Ueckerdt, and D. R. Wood. Planar graphs have bounded queue-number.Journal of the ACM, 67(4):1–38, 2020

work page 2020

Show all 20 references

[9]

Dujmovi´c, P

V. Dujmovi´c, P . Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM Journal on Computing, 34(3):553–579, 2005

2005
[10]

Dujmovi´c and D

V. Dujmovi´c and D. R. Wood. Stacks, queues and tracks: Layouts of graph subdivi- sions.Discrete Mathematics and Theoretical Computer Science, 7:155–202, 2005

2005
[11]

F¨orster, M

H. F¨orster, M. Kaufmann, L. Merker, S. Pupyrev, and C. Raftopoulou. Linear layouts of bipartite planar graphs. In P . Morin and S. Suri, editors,Algorithms and Data Structures, pages 444–459, Cham, 2023. Springer Nature Switzerland

2023
[12]

L. S. Heath, F. T. Leighton, and A. L. Rosenberg. Comparing queues and stacks as machines for laying out graphs.SIAM Journal on Discrete Mathematics, 5(3):398–412, 1992

1992
[13]

L. S. Heath and A. L. Rosenberg. Laying out graphs using queues.SIAM Journal on Computing, 21(5):927–958, 1992

1992
[14]

Katheder, M

J. Katheder, M. Kaufmann, S. Pupyrev, and T. Ueckerdt. Transforming stacks into queues: Mixed and separated layouts of graphs. InSTACS, volume 327 ofLIPIcs, pages 56:1–56:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2025

2025
[15]

Kratochv´ıl and M

J. Kratochv´ıl and M. Vaner. A note on planar partial 3-trees.CoRR, abs/1210.8113, 2012

2012 arXiv
[16]

S. V. Pemmaraju.Exploring the powers of stacks and queues via graph layouts. PhD thesis, Virginia Tech, 1992

1992
[17]

S. Pupyrev. Mixed linear layouts of planar graphs. InInternational Symposium on Graph Drawing and Network Visualization, volume 10692 ofLNCS, pages 197–209. Springer, 2017

2017
[18]

S. Pupyrev. Queue layouts of two-dimensional posets. In P . Angelini and R. von Hanxleden, editors,International Symposium on Graph Drawing and Network Visual- ization, volume 13764 ofLNCS, pages 353–360. Springer, 2022

2022
[19]

Wiechert

V. Wiechert. On the queue-number of graphs with bounded tree-width.Electr. J. Comb., 24(1):P1.65, 2017

2017
[20]

D. R. Wood. Queue layouts of graph products and powers.Discrete Mathematics & Theoretical Computer Science, 7, 2005. 7

2005

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [4]

M. A. Bekos, M. Gronemann, and C. Raftopoulou. An improved upper bound on the queue number of planar graphs.Algorithmica, 85(2):544–562, 2023. 6

work page 2023

[2] [1]

J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees.Algorithmica, 82(9):2564–2585, 2020

work page 2020

[3] [2]

J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. The mixed page number of graphs.Theor. Comput. Sci., 931:131–141, 2022

work page 2022

[4] [3]

Arnborg and A

S. Arnborg and A. Proskurowski. Characterization and recognition of partial 3-trees. SIAM Journal on Algebraic Discrete Methods, 7(2):305–314, 1986

work page 1986

[5] [5]

Di Battista, F

G. Di Battista, F. Frati, and J. Pach. On the queue number of planar graphs.SIAM Journal on Computing, 42(6):2243–2285, 2013

work page 2013

[6] [6]

Dujmovi´c

V. Dujmovi´c. Graph layouts via layered separators.Journal of Combinatorial Theory, Series B, 110:79–89, 2015

work page 2015

[7] [7]

Dujmovi´c and F

V. Dujmovi´c and F. Frati. Stack and queue layouts via layered separators.J. Graph Algorithms Appl., 22(1):89–99, 2018

work page 2018

[8] [8]

Dujmovi´c, G

V. Dujmovi´c, G. Joret, P . Micek, P . Morin, T. Ueckerdt, and D. R. Wood. Planar graphs have bounded queue-number.Journal of the ACM, 67(4):1–38, 2020

work page 2020