Tripod Reordering: A 33-Queue Layout of Planar Graphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Tripod Reordering: A 33-Queue Layout of Planar Graphs".
Jane: Here's the gist of the paper. A tripod reordering technique is presented to improve the queue number bound for planar graphs from 49 to 33 by addressing a limitation in previous approaches.
Tom: Introduction to Queue Layouts and Planar Graphs Queue layouts are defined by a linear order of vertices and a partition of edges into queues such that no two edges in a single queue are nested <ref:2611.14817#pg6> The initial bound of 49 was derived by combining this theorem with Wood’s bounds for queue layouts of graph products <ref:2611.14817#pg6> The Gap in Previous Tripod Reordering Bekos, Gronemann, and Raftopoulou claimed an improvement from 49 to 42 queues for planar graphs by reordering the three vertices associated with each bag in the product structure decomposition <ref:2611.14817#pg6> However, it turned out that one of the choices required by their ordering rule is not guaranteed to exist <ref:2611.148173,Consequently, the published proof in
6: does not establish the claimed upper bound of 42 queues for planar graphs> <ref:2611.14817#pg4> This gap was explained by showing that augmentation can join tripods from different recursive regions into one next-level component, violating the condition required by the ordering rule <ref:2611.14817#pg4> New Construction via Multigraph Expansion The new approach avoids the problematic ordering step by working directly with a multigraph arising from the recursive decomposition <ref:2611.14817#pg4> The key observation is that the resulting vertex order is compatible with the rotation system of this multigraph <ref:2611.14817#pg4> By replacing each vertex of Hb by one vertex for each vertical path of its tripod, the expanded graph Hb△ is shown to have qn(Hb△) ≤ 2 · 5 = 10 <ref:2611.14817#pg4> Final Queue Number Bound and Bipartite Case The final bound is derived by applying the construction underlying the path bound of Claim 1 to Hb△ ⊠ P, yielding qn(G) ≤ 30 + 1 + 2 = 33 <ref:2611.14817#pg8> For bipartite planar graphs, since they have no intra-layer edges, the inter-bag edges use at most 2 · 10 = 20 queues, leading to qn(G) ≤ 2 · 10 + 2 = 22 <ref:2611.14817#pg8> The paper concludes that the tripod reordering construction yields an improved bound of at most 33 for planar graphs <ref:2611.14817#pg8> Substantial gaps remain between the upper and lower bounds for planar graphs, and determining either value remains an open problem <ref:2611.148175,The largest queue number of a planar graph lies between 4
2: and 33> <ref:2611.14817#pg8> The largest queue number for bipartite planar graphs is known to lie between 3
14: and 22 <ref:2611.14817#pg8>.
Jane: Pruning redundant reasoning tokens The paper uses AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8> A full implementation of the 33-queue layout algorithm for planar graphs is available in
20: <ref:2611.14817#pg8>.
Tom: How the training signal is built The proof strategy for Theorem 1 and the main ideas were developed manually by the author following the identification of the gap in
22: <ref:2611.14817#pg8> The author used AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8>.
Paper summary: Tom: So to wrap up this paper, "Tripod Reordering: A thirty-three-Queue Layout of Planar Graphs," it’s essentially showing that we can improve the known upper bound on the queue number for planar graphs from forty nine down to thirty three > <ref:2611.14817#pg1,Tripod Reordering: A 33-Queue Layout of Planar Graphs>
Jane: The authors tackle a problem where previous attempts claimed a better bound of forty two, but they found the specific ordering rule required for that improvement wasn't always possible in practice >
Lu: Their solution bypasses that roadblock by using a multigraph expansion and showing it has less than ten queues, which then combines to give the final thirty three bound >
Meng: It’s about finding a way to get a concrete number when you can’t guarantee an ideal structural choice in the algorithm >
Tom: The implication is that for planar graphs, thirty three is now the best proven upper limit we have, and it's better than what we thought was possible based on older methods >
Jane: They also looked at bipartite planar graphs and found a tighter bound of twenty two there, because they don't have those intra-layer edges that complicate things for them >
Lu: The main point is that this specific tripod reordering construction prevents a three rainbow structure in the expanded graph, which is the mechanism that gets us to thirty three >
Meng: It tells us how to deploy these layout algorithms with a more predictable performance ceiling when dealing with planar structures at scale >
Conclusion: Tom: So we're wrapping up this look at "Tripod Reordering: A thirty-three-Queue Layout of Planar Graphs." Basically, they took an older method that gave them a forty nine queue bound and they found a new way to get it down to thirty three.
Jane: That's right. The core idea is about reordering how things are arranged in the graph decomposition, specifically those tripods associated with each bag in the product structure. It’s a structural trick that fixes an issue where previous attempts couldn't guarantee that specific ordering choice existed for every setup.
Lu: Exactly. The authors show they can bypass that problematic ordering step by working directly with a multigraph expansion from the recursive decomposition, and they prove this new expanded graph has a very small queue number bound of less than ten.
Meng: So it’s not just a neat trick in the ordering; it’s about changing how you model the problem entirely by expanding the graph structure, and that expansion keeps things manageable for practical deployment.
Tom: And that expansion leads to their final result: a thirty three queue bound for general planar graphs. That's better than forty nine. The paper also looks at bipartite planar graphs and gets a tighter number of twenty two there because they don't have those extra edges that cause problems.
Jane: It shows how even in these complex geometric structures, finding the right way to order the pieces can actually give you a significant improvement on the known limits. It tells us that the naive question of what's possible is often limited by tricky structural choices in our algorithms.
Lu: What this really changes for researchers is seeing that augmentation, which was used in prior work, can be joined into a single next-level component without violating those ordering rules, which was the gap they found earlier.
Meng: From an engineering standpoint, it means if you're designing a system based on these layouts, you have a much more predictable performance ceiling now because the structural choices are less arbitrary.
Tom: It's about moving from forty nine down to thirty three with a concrete construction, and that construction is what matters here. We’ve seen how this specific vertex ordering choice prevents a three rainbow structure in the expanded graph, which is the mechanism that gets us to that thirty three number.
Jane: So, it’s not just about getting a better theoretical number; it’s about understanding *why* the previous attempts failed and building a method where you can control those structural choices more reliably. This opens up new avenues for how we analyze these graph structures in general.
cs.DM, cs.DS, math.CO
Submitted: 2026-11-10
Updated: 2026-11-10
Code: https://github.com/spupyrev/bob
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 81/100
The gist: A tripod reordering technique is presented to improve the queue number bound for planar graphs from 49 to 33 by addressing a limitation in previous approaches.
Key concepts
- Queue Layouts
- A queue layout is a way to order vertices linearly and partition edges into queues such that no two edges within the same queue are nested. This structure is fundamental to analyzing how edges are arranged in a graph.
- Tripod Reordering
- This technique involves reordering the three vertices associated with each bag in a product structure decomposition. The new approach uses this reordering strategically to ensure that certain problematic edge configurations, like 3-rainbows, do not occur, leading to a tighter bound.
- Multigraph Expansion (Hb△)
- The paper avoids the difficult ordering step by working directly with a multigraph derived from the recursive decomposition. By replacing each vertex of Hb with one vertex for every vertical path of its tripod, this expanded graph is shown to have a small queue number, which is key to establishing the final bound.
- Queue Number Bound (qn(G))
- The queue number bound represents the maximum possible number of queues required in a valid queue layout for a given graph G. The goal of the paper is to find an upper limit for this value, specifically showing that for planar graphs, this bound can be at most 33.
Terminology
Summary
A tripod reordering technique is presented to improve the queue number bound for planar graphs from 49 to 33 by addressing a limitation in previous approaches. p. 0 We first highlight a gap in their queue layout algorithm:
one of the choices required by the algorithm is not guaranteed to exist. Then we show
how to address the limitation and provide an alternative tripod reordering mechanism
that reduces the upper bound on the queue number of planar graphs to 33.Where the paper says it
Introduction to Queue Layouts and Planar Graphs
Queue layouts are defined by a linear order of vertices and a partition of edges into queues such that no two edges in a single queue are nested <ref:2611.14817#pg6> The initial bound of 49 was derived by combining this theorem with Wood’s bounds for queue layouts of graph products <ref:2611. p. 1 Their proof uses the planar product structure theorem: every planar graph is a subgraph
of the strong product of a graph of simple treewidth at most 3, a clique K3, and a path. Combining this theorem with Wood’s bounds for queue layouts of graph products [24]
gives the constant 49.Where the paper says it
The Gap in Previous Tripod Reordering
Bekos, Gronemann, and Raftopoulou claimed an improvement from 49 to 42 queues for planar graphs by reordering the three vertices associated with each bag in the product structure decomposition <ref:2611.14817#pg6> However, it turned out that one of the choices required by their ordering rule is not guaranteed to exist <ref:2611. p. 1 Their
argument uses the freedom to reorder the three vertices associated with each tripod (a bag
in the product structure decomposition); we refer to this optimization as tripod reordering. Unfortunately, it turned out that one of the choices required by their ordering rule is
not guaranteed to exist. Unfortunately, it turned out that one of the choices required by their ordering rule is
not guaranteed to exist. Consequently, the published proof in [6] does not establish the
claimed upper bound of 42 queues for planar graphs. Before applying P3T, the algorithm subdivides loops and parallel
edges in the quotient and augments the resulting simple graph to a maximal plane 3-tree. This augmentation can join tripods from different recursive regions into one next-level
component, violating the condition required by the ordering rule.Where the paper says it
Where the paper says it
Where the paper says it
New Construction via Multigraph Expansion
The new approach avoids the problematic ordering step by working directly with a multigraph arising from the recursive decomposition <ref:2611.14817#pg4> The key observation is that the resulting vertex order is compatible with the rotation system of this multigraph <ref:2611. p. 1 The main difference
is that we work directly with a multigraph arising from the recursive decomposition,
avoiding the problematic ordering step. The key observation is that the resulting vertex
order is compatible with the rotation system of this multigraph. 3, allows
us to choose the order of the three vertical paths of each tripod so as to reduce the number
of queues needed after expansion. Replacing each vertex of Hb by one vertex for each
vertical path of its tripod gives an expanded graph Hb△.Where the paper says it
Where the paper says it
Final Queue Number Bound and Bipartite Case
The final bound is derived by applying the construction underlying the path bound of Claim 1 to Hb△ ⊠ P, yielding qn(G) ≤ 30 + 1 + 2 = 33 <ref:2611.14817#pg8> For bipartite planar graphs, since they have no intra-layer edges, the inter-bag edges use at most 2 · 10 = 20 queues, leading to qn(G) ≤ 2 · 10 + 2 = 22 <ref:2611. p. 5 The inter-bag edges are divided into three types:
intra-layer edges and inter-layer edges in the two directions of the vertex order of H. Without reordering, each type uses ℓ · qn(H) ≤ 3 · 5 = 15 queues, since the layered width is
ℓ = 3 and H has a 5-queue layout.Where the paper says it
Conclusion and Open Problems
The paper concludes that the tripod reordering construction yields an improved bound of at most 33 for planar graphs <ref:2611.14817#pg8> Substantial gaps remain between the upper and lower bounds for planar graphs, and determining either value remains an open problem <ref:2611. p. 0 Di Battista, Frati, and Pach [7] and Dujmovic [ ´ 8] obtained logarithmic upper bounds. Subsequently, Bekos, Forster, Gronemann, Mchedlidze, Montecchiani, Raftopoulou, and ¨
Ueckerdt showed that planar graphs of bounded maximum degree have constant queue
1
arXiv:2611. Di Battista, Frati, and Pach [7] and Dujmovic [ ´ 8] obtained logarithmic upper bounds. Subsequently, Bekos, Forster, Gronemann, Mchedlidze, Montecchiani, Raftopoulou, and ¨
Ueckerdt showed that planar graphs of bounded maximum degree have constant queue
1
arXiv:2611. Then we show
how to address the limitation and provide an alternative tripod reordering mechanism
that reduces the upper bound on the queue number of planar graphs to 33. As a
corollary, bipartite planar graphs have queue number at most 22.Where the paper says it
Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The paper uses AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8> A full implementation of the 33-queue layout algorithm for planar graphs is available in [20] <ref:2611. p. 1 We provide a full implementation of the 33-queue layout algorithm in [20]. Following the work of Forster, Kaufmann, Merker, Pupyrev, and Raftopoulou [ ¨ 14], we
can transfer our upper bound to bipartite planar graphs.Where the paper says it
How the training signal is built
The proof strategy for Theorem 1 and the main ideas were developed manually by the author following the identification of the gap in [22] <ref:2611.14817#pg8> The author used AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8>.
Where the gains come from
The gains come from choosing a new vertex order for each tripod that prevents three edges corresponding to one queue of Hb from forming a 3-rainbow in Hb△ <ref:2611.14817#pg4> This leads to the final bound of qn(G) ≤ 30 + 1 + 2 = 33 <ref:2611. p. 0 Di Battista, Frati, and Pach [7] and Dujmovic [ ´ 8] obtained logarithmic upper bounds. Subsequently, Bekos, Forster, Gronemann, Mchedlidze, Montecchiani, Raftopoulou, and ¨
Ueckerdt showed that planar graphs of bounded maximum degree have constant queue
1
arXiv:2611.Where the paper says it
The paper uses AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8>.
The paper uses AI tools, such as ChatGPT Codex (Sol/Astra) and Claude Code (Opus/Fable), for checking proof arguments, proofreading, editing the manuscript, and implementing the algorithm <ref:2611.14817#pg8>.
The gains come from choosing a new vertex order for each tripod that prevents three edges corresponding to one queue of Hb from forming a 3-rainbow in Hb△ <ref:2611.14817#pg4>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve layout algorithms for planar graphs by implementing a tripod reordering mechanism that reduces the upper bound on queue number from 49 to 33 by showing
an alternative tripod reordering mechanism that reduces the upper bound on the queue number of planar graphs to 33.
-
Develop a system capable of finding an H-partition of layered width at most 3 for a planar graph G, where H is a partial planar 3-tree, using the PPS algorithm and P3T algorithm to establish bounds based on
Claim 1 (Theorem 7 of [24], Lemma 9 of [10]).
-
Create an optimized layout construction method that works directly with a multigraph arising from recursive decomposition, avoiding the
problematic ordering step,
and utilizes vertex order compatible with the rotation system to achieve the improved bound. -
Implement a P3T d algorithm that extends to multigraphs by working directly with "Hb
and utilizing Lemma 1, which states that for every vertex u in Hb,
the incidences belonging to each port of u are consecutive in the rotation at u." -
Design a system capable of determining the correct port order for a tripod vertex based on whether an interval meets all three ports, using the derived ordering "If It(u) meets the three ports, we read it clockwise from its first incidence. We name the first encountered port alpha, the next distinct port beta, and the remaining port gamma, and set beta < u alpha < gamma."
-
Enhance layout algorithms for bipartite planar graphs by adapting Theorem 1 to show that
Every bipartite planar graph has queue number at most 22,
by using the argument of [14] and noting thatG is bipartite, it has no intra-layer edges.
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. A planar product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood (JACM, 2020) 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. The result has been used to show 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 an appropriate reordering of the three vertices associated with each bag in the product structure decomposition, called a tripod, reduces the queue number of planar graphs to 42. We first highlight a gap in their queue layout algorithm: one of the choices required by the algorithm is not guaranteed to exist. Then we show how to address the limitation and provide an alternative tripod reordering mechanism that reduces the upper bound on the queue number of planar graphs to 33. As a corollary, bipartite planar graphs have queue number at most 22.
Sources
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns