Pith. sign in

REVIEW 2 major objections 4 minor 60 references

Short Paths in the Planar Graph Product Structure Theorem

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Every planar graph has a bounded-treewidth product with a short path factor.

desk verdict First o(n) bound on the path length in the planar product structure theorem, but the proof of the key counting lemma (Lemma 18) has a genuine flaw that currently invalidates the main theorem. read the letter →

arxiv 2502.01927 v1 pith:SSNLOU6N submitted 2025-02-04 math.CO

Kevin Hendrey , David R. Wood This is my paper · ORCID
classification math.CO MSC 05C1005C8305C75
keywords planargraphproductstructuretheoremtreewidthstrongofgraphslayeredtree-decompositiontree-partitionweakdiametertriangulationpathlengthbound
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 paper answers the question, left open after the Planar Graph Product Structure Theorem, of how short the path $P$ can be in a containment $G \subseteq H \boxtimes P \boxtimes K_c$. It proves that for every $\epsilon \in (0,1/2)$ and every $n$-vertex planar graph $G$, there is a planar graph $H$ of treewidth at most $3$ and a path $P$ with $|V(P)| \le (9/\epsilon+15)(\mathrm{tw}(G)+1)^{1-\epsilon} n^{\epsilon}$ such that $G$ is contained in $H \boxtimes P \boxtimes K_c$ for $c \le 24+8/\epsilon$. Because $\mathrm{tw}(G)=O(\sqrt n)$ for planar graphs, this is the first $o(n)$ upper bound on the path length, and it is almost tight against the known $\Omega(\sqrt n)$ lower bound. Taking $\epsilon=1/\log n$ gives a path of length $O(\mathrm{tw}(G)\log n)$ with $c=O(\log n)$, so the product $H \boxtimes P \boxtimes K_c$ has treewidth within a $O(\log^2 n)$ factor of $\mathrm{tw}(G)$.

What carries the argument

The engine is Lemma 16, a tree-partition of a planar triangulation whose parts are the connected components of the distance layers from a chosen root; the quotient is a tree and every part has weak-diameter at most $3\,\mathrm{tw}(G)+2$. Around this, the proof defines a seed $(S,f)$, a set of root vertices with layer offsets satisfying $|f(v)-f(w)| \ge \mathrm{dist}_G(v,w)$, which generates a layering by taking the neighbours of the previous layer and adding fresh roots at prescribed offsets. Lemma 18 packs upward paths of length $k$ in a rooted tree with a bound on how many packing paths a root-to-vertex path can contain, and Lemma 19 combines the seed and the packing to produce a spanning forest whose components every edge-path in the spanning tree meets at most $\lceil 1/\epsilon \rceil+2$ times. Lemma 17 then shows each bag of the induced tree-decomposition contains at most $12+4/\epsilon$ vertices of each layer, the exact input needed for the product-conversion theorems.

What would settle it

Enumerate planar triangulations up to a modest size and test Lemma 16 directly: in the tree-partition whose parts are the connected components of each distance layer from a root $r$, search for two vertices in one part with $\mathrm{dist}_G(v,w)>3\,\mathrm{tw}(G)+2$, or for a component $C$ of $G[V_i \cup V_{i+1} \cup \cdots]$ whose boundary contains a vertex of $V_i$ not adjacent to the part of $C$ in $V_{i-1}$; either event would refute the load-bearing lemma and the current proof of the theorem.

Watch

Extended reading notes

Core claim

The central discovery is that planar graphs admit layered tree-decompositions with few layers: Lemma 9 bounds the number of layers by $(9/\epsilon+15)(\mathrm{tw}(G)+1)^{1-\epsilon} n^{\epsilon}$ and the intersection of each bag with each layer by $12+4/\epsilon$. By the $H$-partition conversion theorems of Section 3, such a layered tree-decomposition is equivalent to containment in $H \boxtimes P \boxtimes K_c$ with $H$ of simple treewidth at most $3$ and $|V(P)|$ at most the number of layers. The proof turns the path-length problem into a layering problem: find a spanning tree and a layering of the triangulated graph so that the tree-path of every edge crosses only a bounded number of forest components. The layering is generated by a seed construction that repeatedly introduces fresh roots at the next layer, after Lemma 16 shows that the tree-partition coming from BFS layers has weak-diameter at most $3\,\mathrm{tw}(G)+2$. The resulting theorem asserts the path can be as short as $O((\mathrm{tw}(G)+1)^{1-\epsilon} n^{\epsilon})$, with the clique factor $c$ absorbing the $O(1/\epsilon)$ dependence.

Load-bearing premise

The proof depends on the unproved claim that, when the vertices of a planar triangulation are arranged by distance from a root, each block of the resulting tree partition is surrounded only by vertices from the previous distance layer, rather than by vertices from other blocks of the same layer; if that failed, the bound on block diameter would collapse and with it the whole path-length construction.

Editorial extensions

If this is right

  • For any $\epsilon \in (0,1/2)$, every $n$-vertex planar graph is contained in $H \boxtimes P \boxtimes K_{O(1/\epsilon)}$ with $|V(P)|=O((1/\epsilon)(\mathrm{tw}(G)+1)^{1-\epsilon} n^{\epsilon})$; this is the first $o(n)$ bound on the path factor and is tight up to the $O((1/\epsilon)n^{\epsilon})$ factor.
  • With $\epsilon=1/\log n$, the same theorem gives $|V(P)|=O(\mathrm{tw}(G)\log n)$ and $c=O(\log n)$, so $H \boxtimes P \boxtimes K_c$ has treewidth within an $O(\log^2 n)$ factor of $\mathrm{tw}(G)$.
  • Lemma 16, stated as a result of independent interest, gives every planar triangulation a parent-dominated tree-partition of width at most $3\,\mathrm{tw}(G)+2$ whose parts have weak-diameter $O(\mathrm{tw}(G))$.
  • The Section 6 machinery transfers the short-path theorem to fan-planar graphs, $k$-planar graphs, and powers of bounded-degree planar graphs, with comparable sublinear path bounds.

Reading between the lines

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

  • If the theorem stands, applications that currently invoke the product structure theorem with a path of length up to $n$, such as queue layouts, adjacency labelling, or centred colourings, are candidates for re-derivation with improved dependence on $n$; the paper does not carry out these re-derivations.
  • The weak-diameter tree-partition lemma is proved only for planar triangulations; an analogous construction for bounded-genus graphs or for apex-minor-free classes would be a natural route to short-path product theorems beyond the planar case.
  • The bound's $\epsilon \to 0$ limit suggests that reducing the path length to the paper's open targets $O(\sqrt n)$ or $O(\mathrm{tw}(G))$ would require a construction not based on the same seed-layering trade-off between clique factor and path length.
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.

Referee Report

2 major / 4 minor

Summary. The paper addresses the question of how short the path P can be in the Planar Graph Product Structure Theorem, which states that every planar graph G is contained in H ⊠ P ⊠ K_3 with H of treewidth at most 3. The authors prove an upper bound |V(P)| = O((1/ε) tw(G) n^ε) for every ε ∈ (0,1/2), improving the previously known trivial O(n) bound and nearly matching the Ω(tw(G)) lower bound. The proof works by constructing a layered tree-decomposition with few layers and bounded bag-layer intersections, then applying results of Illingworth, Scott, and Wood to convert this into a product structure. The paper also gives corollaries for fan-planar graphs, k-planar graphs, and powers of bounded-degree planar graphs, and states several open problems.

Significance. If the main theorem is correct, it answers a natural question that has been asked by several researchers and gives the first o(n) upper bound on the path length in the planar product structure theorem. The stronger bound in terms of tw(G) is particularly appealing and is nearly tight. The paper is well organized and provides full proofs, and the extensions to beyond-planar classes are useful. However, the proof of the central combinatorial lemma, Lemma 18, contains a false estimate, and since Lemma 19 and Lemma 9 depend on it, the main theorem is not established as written. The existential statement of Lemma 18 may still be true, but the manuscript needs a corrected proof before the results can be accepted.

major comments (2)
  1. [§5, Lemma 18] The proof of Lemma 18 is invalid. The key assertion is: 'It follows that for each i ∈ [τ], there are at most 2(n/k)^(1/τ) edges uv in E(P) \ E∗ such that k(n/k)^(i/τ) ≥ w(u) > k(n/k)^((i−1)/τ).' This is false. For a concrete example, take τ=2, k=10, n=100000, so a=(n/k)^(1/τ)=100. Construct a rooted tree whose main root-to-leaf path has 15334 edges, and attach a pendant subtree of 59 vertices to the upper endpoint of every tenth edge, for 1435 such edges; attach nothing to the other path edges. The total vertex count is 15335 + 1435·59 = 100000. Along the main path, the weights decrease from 100000 to 1; the 1435 special edges each have weight drop 60, the nine edges before each have drop 1, and the remaining 984 tail edges have drop 1 with weights below 1000. In the graph (V(T),E∗), every maximal E∗-path on the main path has length 9, because the drop-60 edges are not in E∗ and the tail edges below weight 1000 are not in E∗. Hence the proof's construction yields no length-10 path in U, so U = {r}. For the leaf v, c_v = 0, but |E(T_{r,v})| = 15334 > (3·2·100+1)·10 = 6010, contradicting property (2) for the constructed U. In particular, there are 1435 non-E∗ edges with parent weight in the interval (1000,100000], far exceeding the claimed 2a = 200. This shows the proof of Lemma 18 does not establish the lemma. Since Lemma 19 applies Lemma 18 and Lemma 9 relies on Lemma 19, the proof of Theorem 3 is incomplete. The counterexample does not necessarily disprove the existential statement of Lemma 18, because a different choice of U could satisfy property (2); however, the manuscript provides no such correct construction.
  2. [§4, Lemma 16] The sentence 'Every vertex that is not in C and is adjacent to a vertex in C is in S' is asserted without proof. The component C of G[V_i ∪ V_{i+1} ∪ ...] containing B_x may contain several components of G[V_i] that are connected through higher layers, and a vertex in V_{i-1} adjacent to one of those other components need not be adjacent to B_x. If such a vertex exists, then S does not separate C from {r}, and the subsequent minimality argument and the conclusion that T is a tree would fail. The proof should justify this separation claim explicitly or define C differently. This point is load-bearing because Lemma 16 is used in Lemma 19, which in turn feeds Lemma 9.
minor comments (4)
  1. [Abstract] The abstract states the result for ε ∈ (0,1), but Theorems 2 and 3 are stated for ε ∈ (0,1/2); the abstract should match the theorem statements.
  2. [§4, Lemma 15] The statement says 'connected subgraphs H1 and H1'; the second H1 should be H2.
  3. [§5, Lemma 9 proof] The phrase 'which which we restate here' contains a duplicated 'which'.
  4. [§6, Theorem 22] The proof says fan-planar graphs have 'average degree less than 10n'; this should be 'less than 10' (or 'at most 5n−10 edges'), since the average degree is a constant independent of n.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the short-path product bound is derived from new tree-partition and seed lemmas, with prior theorems used as external tools.

full rationale

The paper's central derivation is not circular. Theorem 3 follows from Lemma 9 (a new bound on the number of layers in a layered tree-decomposition) and Lemma 14, which is an immediate corollary of Illingworth-Scott-Wood Theorem 13. Theorem 13 is an external result about H-partitions from tree-decompositions of K*_{s,t}-minor-free graphs; its statement does not involve path length, product structure, or any version of the target bound. Similarly, Theorem 10 is used only to derive the non-planar-H variant, and Lemma 20 is used only for the beyond-planar extensions; neither assumes the short-path theorem. Observation 8 is a standard definitional equivalence between product containment and layered partitions, not a self-definition of the proved quantity. Lemma 9 itself is built from Lemma 16 (tree-partition weak-diameter, proved from treewidth duality and a planar separation lemma), Lemma 18 (an elementary weighted-tree lemma), and Lemma 19 (seed construction); these are new arguments with explicit constants and no fitted parameters. The parameter epsilon is universally quantified, not tuned to force the conclusion. The concerns raised in the reader's notes about Lemma 16 and Lemma 18 are potential correctness gaps in the proof, not circularity: even if a lemma were false or underproved, the derivation would be invalid rather than equivalent to its inputs. No step in the paper reduces, by construction or by self-citation, to the result it claims to establish. Hence the appropriate circularity score is 0.

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

The proof relies on standard graph-theoretic tools and on three cited structural theorems from the same research group. These are published or arXiv results not derived in this paper. No parameter is fitted to data; all constants are explicit functions of ε and tw(G).

assumptions (6)
  • standard math Treewidth Duality Theorem (Seymour-Thomas): tw(G)+1 = bn(G)
    Used in Lemma 16 to turn the existence of a large bramble into a lower bound on treewidth.
  • standard math Menger's theorem on vertex-disjoint paths and separators
    Used in Lemma 16 to derive k+1 disjoint paths between B_i and B_{i-k} or a small separator.
  • standard math von Staudt's theorem: the edges of a plane triangulation not in a spanning tree T form a spanning tree T* of the dual
    Basis of the Eppstein-style tree-decomposition in Lemma 7.
  • domain assumption Lemma 6 (Biedl-Velázquez): every planar graph can be triangulated without increasing treewidth
    Invoked in Lemma 9 to reduce to planar triangulations while preserving tw(G).
  • domain assumption Theorem 10/Theorem 13 (Illingworth-Scott-Wood): J_{s,t}-minor-free and K*_{s,t}-minor-free graphs admit H-partitions of bounded D-width with H of bounded (simple) treewidth
    The bridge from a layered tree-decomposition (Lemma 9) to the product form in Theorem 3; note significant author overlap with the present paper.
  • domain assumption Lemma 20 (Hickingbotham-Wood): r-shallow minors inherit product structure
    Used in Section 6 to transfer the planar short-path theorem to fan-planar, k-planar, and graph powers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Short Paths in the Planar Graph Product Structure Theorem." pith.science (2026). https://pith.science/paper/SSNLOU6N

@misc{pith2026250201927,
  author       = {Pith},
  title        = {Pith review of: Short Paths in the Planar Graph Product Structure Theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SSNLOU6N}},
  note         = {Machine review of arXiv:2502.01927}
}
abstract

The Planar Graph Product Structure Theorem of Dujmovi\'c et al. [J. ACM '20] says that every planar graph $G$ is contained in $H\boxtimes P\boxtimes K_3$ for some planar graph $H$ with treewidth at most 3 and some path $P$. This result has been the key to solving several old open problems. Several people have asked whether the Planar Graph Product Structure Theorem can be proved with good upper bounds on the length of $P$. No $o(n)$ upper bound was previously known for $n$-vertex planar graphs. We answer this question in the affirmative, by proving that for any $\epsilon\in (0,1)$ every $n$-vertex planar graph is contained in $H\boxtimes P\boxtimes K_{O(1/\epsilon)}$, for some planar graph $H$ with treewidth 3 and for some path $P$ of length $O(\frac{1}{\epsilon}n^{(1+\epsilon)/2})$. This bound is almost tight since there is a lower bound of $\Omega(n^{1/2})$ for certain $n$-vertex planar graphs. In fact, we prove a stronger result with $P$ of length $O(\frac{1}{\epsilon}\,\textrm{tw}(G)\,n^{\epsilon})$, which is tight up to the $O(\frac{1}{\epsilon}\,n^{\epsilon})$ factor for every $n$-vertex planar graph $G$. Finally, taking $\epsilon=\frac{1}{\log n}$, we show that every $n$-vertex planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{O(\log n)}$ for some planar graph $H$ with treewidth at most 3 and some path $P$ of length $O(\textrm{tw}(G)\,\log n)$. This result is particularly attractive since the treewidth of the product $H\boxtimes P\boxtimes K_{O(\log n)}$ is within a $O(\log^2n)$ factor of the treewidth of $G$.

Figures

Figures reproduced from arXiv: 2502.01927 by the authors.

Figure 1
Figure 1. Strong product of two paths. V (A) × V (B), where distinct vertices (v, x) and (w, y) are adjacent if: • v = w and xy ∈ E(B), or • x = y and vw ∈ E(A), or • vw ∈ E(A) and xy ∈ E(B). The following Planar Graph Product Structure Theorem is the classical example of a graph prod￾uct structure theorem. Here, a graph H is con￾tained in a graph G if H is isomorphic to a sub￾graph of G, written H ⊂∼ G. Theorem 1. For every … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 47 canonical work pages

  1. [1]

    Characterization and recognition of partial 3-trees

    Stef an Arnborg and Andrzej Proskurowski . Characterization and recognition of partial 3-trees. SIAM J. Algebraic Discrete Methods, 7(2):305–314, 1986

    work page 1986

  2. [2]

    Bekos and Luca Grilli

    Michael A. Bekos and Luca Grilli . Fan-planar graphs. InSeok-Hee Hong and Takeshi Tokuyama, eds.,Beyond Planar Graphs, pp. 131–148. Springer, 2020

    work page 2020

  3. [3]

    Bekos, Giordano Da Lozzo, Petr Hlinený, and Michael Kaufmann

    Michael A. Bekos, Giordano Da Lozzo, Petr Hlinený, and Michael Kaufmann . Graph product structure forh-framed graphs. Electron. J. Comb., 31(4), 2024

    work page 2024

  4. [4]

    Drawing planar 3-trees with given face areas

    Therese Biedl and Lesvia Elena Ruiz Velázquez . Drawing planar 3-trees with given face areas. Comput. Geom., 46(3):276–285, 2013

    2013

  5. [5]

    Bodlaender

    Hans L. Bodlaender . A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1–45, 1998

    work page 1998

  6. [6]

    Bodlaender

    Hans L. Bodlaender . A note on domino treewidth. Discrete Math. Theor. Comput. Sci., 3(4):141–150, 1999

    work page 1999

  7. [7]

    Bodlaender and Joost Engelfriet

    Hans L. Bodlaender and Joost Engelfriet . Domino treewidth.J. Algorithms, 24(1):94–123, 1997

    work page 1997

  8. [8]

    Bodlaender, Carla Groenland, and Hugo Jacob

    Hans L. Bodlaender, Carla Groenland, and Hugo Jacob . On the parameterized complexity of computing tree-partitions. InHolger Dell and Jesper Nederlof , eds.,Proc. 17th International Symposium on Parameterized and Exact Computation(IPEC 2022), vol. 249 of LIPIcs, pp. 7:1–7:20. Schloss Dagstuhl, 2022

    work page 2022

Show all 60 references
  1. [9]

    Shorter labeling schemes for planar graphs

    Marthe Bonamy, Cyril Ga voille, and Michał Pilipczuk . Shorter labeling schemes for planar graphs. SIAM J. Discrete Math., 36(3):2082–2099, 2022

    2022

  2. [10]

    Pruessmann, Anusch Taraz, and Andreas Würfl

    Julia Böttcher, Klaas P. Pruessmann, Anusch Taraz, and Andreas Würfl . Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs.European J. Combin., 31(5):1217–1227, 2010

    2010

  3. [11]

    Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and Da vid R

    Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and Da vid R. Wood. Product structure of graph classes with bounded treewidth.Combin. Probab. Comput., 33(3):351–376,...

    2024

  4. [12]

    Apollonian ball packings and stacked polytopes.Discrete Comput

    Hao Chen. Apollonian ball packings and stacked polytopes.Discrete Comput. Geom., 55(4):801– 826, 2016

    2016

  5. [13]

    The thickness of fan-planar graphs is at most three

    Otfried Cheong, Maximilian Pfister, and Lena Schlipf . The thickness of fan-planar graphs is at most three. InPatrizio Angelini and Reinhard von Hanxleden , eds.,Proc. 30th International Symposium on Graph Drawing and Network Visualization(GD 2022), vol. 13764 of Lecture Notes...

    2022

  6. [14]

    Some results on tree decomposition of graphs.J

    Guoli Ding and Bogdan Oporowski . Some results on tree decomposition of graphs.J. Graph Theory, 20(4):481–499, 1995

    1995

  7. [15]

    On tree-partitions of graphs.Discrete Math., 149(1– 3):45–58, 1996

    Guoli Ding and Bogdan Oporowski . On tree-partitions of graphs.Discrete Math., 149(1– 3):45–58, 1996

    1996

  8. [16]

    Marc Distel, Robert Hickingbotham, Tony Huynh, and Da vid R. Wood . Improved product structure for graphs on surfaces.Discrete Math. Theor. Comput. Sci., 24(2):#6, 2022

    2022

  9. [17]

    Seweryn, and Da vid R

    Marc Distel, Robert Hickingbotham, Michał T. Seweryn, and Da vid R. Wood . Powers of planar graphs, product structure, and blocking partitions.Innovations in Graph Theory, 1:39–86, 2024

    2024

  10. [18]

    Marc Distel and Da vid R. Wood . Tree-partitions with bounded degree trees. InDa vid R. Wood, Jan de Gier, and Cheryl E. Praeger , eds.,2021–2022 MATRIX Annals, pp. 203–212. Springer, 2024

    2021

  11. [19]

    Improved bounds for centered colorings.Adv

    Michał Dębski, Stef an Felsner, Piotr Micek, and Felix Schröder . Improved bounds for centered colorings.Adv. Comb., #8, 2021

    2021

  12. [20]

    Size-Ramsey numbers of structurally sparse graphs

    Nemanja Draganić, Marc Kaufmann, Da vid Munhá Correia, Kalina Petrov a, and Raphael Steiner. Size-Ramsey numbers of structurally sparse graphs. 2023, arXiv:2307.12028

    2023 arXiv

  13. [21]

    Adjacency labelling for planar graphs (and beyond).J

    Vida Dujmović, Louis Esperet, Cyril Ga voille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond).J. ACM, 68(6):#42, 2021

    2021

  14. [22]

    Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz W alczak, and Da vid R. Wood. Planar graphs have bounded nonrepetitive chromatic number.Adv. Comb., #5, 2020

    2020

  15. [23]

    Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and Da vid R. Wood . The grid-minor theorem revisited. InProc. 2024 Annual ACM-SIAM Symposium on Discrete Algorithms(SODA ’24), pp. 1241–1245. 2023. arXiv:2307.02816

    2024 arXiv

  16. [24]

    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and Da vid R. Wood. Planar graphs have bounded queue-number.J. ACM, 67(4):#22, 2020

    2020

  17. [25]

    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and Da vid R. Wood . Planar graphs in blowups of fans. InProc. Annual ACM-SIAM Symp. on Discrete Algorithms(SODA ’25), pp. 3382–3391. 2025

    2025

  18. [26]

    Vida Dujmović, Pat Morin, and Da vid R. Wood . Layered separators in minor-closed graph classes with applications.J. Combin. Theory Ser. B, 127:111–147, 2017. arXiv:1306.1595

    2017 arXiv

  19. [27]

    Vida Dujmović, Pat Morin, and Da vid R. Wood . Graph product structure for non-minor- closed classes. J. Combin. Theory Ser. B, 162:34–67, 2023

    2023

  20. [28]

    Wood, and Da vid Worley

    Vida Dujmovic, Pat Morin, Da vid R. Wood, and Da vid Worley . Grid minors and products. 2024, arXiv:2402.14181

    2024 arXiv

  21. [29]

    On comparable box dimension

    Zdenek Dvorák, Daniel Gonçal ves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt . On comparable box dimension. InXa vier Goaoc and Michael Kerber , eds.,Proc. 38th Int’l Symp. on Computat. Geometry(SoCG 2022), vol. 224 ofLIPIcs, pp. 38:1–38:14. Schloss Dagstuhl, 2022

    2022

  22. [30]

    On fractional fragility rates of graph classes

    Zdeněk Dvořák and Jean-Sébastien Sereni . On fractional fragility rates of graph classes. Electronic J. Combinatorics, 27:P4.9, 2020

    2020

  23. [31]

    Quotient tree partitioning of undirected graphs.BIT, 26(2):148–155, 1986

    Anders Edenbrandt. Quotient tree partitioning of undirected graphs.BIT, 26(2):148–155, 1986

    1986

  24. [32]

    Subgraph isomorphism in planar graphs and related problems

    Da vid Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl., 3(3):1–27, 1999

    1999

  25. [33]

    Sparse universal graphs for planarity.J

    Louis Esperet, Gwenaël Joret, and Pat Morin . Sparse universal graphs for planarity.J. London Math. Soc., 108(4):1333–1357, 2023. 19

    2023

  26. [34]

    Tsourakakis

    Alan Frieze and Charalampos E. Tsourakakis . Some properties of random Apollonian networks. Internet Math., 10(1-2):162–187, 2014

    2014

  27. [35]

    3D-grids are not transducible from planar graphs

    Jakub Gajarský, Michał Pilipczuk, and Filip Pokrývka . 3D-grids are not transducible from planar graphs. 2025, arXiv:2501.07558

    2025 arXiv

  28. [36]

    Simpler adjacency labeling for planar graphs with B-trees

    Pa wel Ga wrychowski and Wojciech Janczewski. Simpler adjacency labeling for planar graphs with B-trees. InKarl Bringmann and Timothy M. Chan , eds.,Proc. 5th Symposium on Simplicity in Algorithms(SOSA@SODA 2022), pp. 24–36. SIAM, 2022

    2022

  29. [37]

    Tree-partitions of infinite graphs.Discrete Math., 97:203–217, 1991

    Rudolf Halin. Tree-partitions of infinite graphs.Discrete Math., 97:203–217, 1991

    1991

  30. [38]

    Har vey and Da vid R

    Daniel J. Har vey and Da vid R. Wood . Parameters tied to treewidth. J. Graph Theory, 84(4):364–385, 2017

    2017

  31. [39]

    Robert Hickingbotham and Da vid R. Wood . Shallow minors, graph products and beyond- planar graphs. SIAM J. Discrete Math., 38(1):1057–1089, 2024

    2024

  32. [40]

    H-clique-width and a hereditary analogue of product structure

    Petr Hliněný and Jan Jedelský . H-clique-width and a hereditary analogue of product structure. In Rastisla v Královič and Antonín Kučera , eds., Proc. 49th Int’l Symp. on Math. Foundations of Comput. Sci.(MFCS 2024), vol. 306 ofLIPIcs, pp. 61:1–61:16. Schloss Dagstuhl, 2024

    2024

  33. [41]

    Transductions of graph classes admitting product structure

    Petr Hliněný and Jan Jedelský . Transductions of graph classes admitting product structure. 2025, arXiv:2501.18326

    2025 arXiv

  34. [42]

    Tony Huynh, Bojan Mohar, Robert Šámal, Carsten Thomassen, and Da vid R. Wood . Universality in minor-closed graph classes. 2021, arXiv:2109.00327

    2021 arXiv

  35. [43]

    Freddie Illingworth, Alex Scott, and Da vid R. Wood . Product structure of graphs with an excluded minor. 2022, arXiv:2104.06627

    2022 arXiv

  36. [44]

    Freddie Illingworth, Alex Scott, and Da vid R. Wood . Product structure of graphs with an excluded minor.Trans. Amer. Math. Soc. Ser. B, 11:1233–1248, 2024

    2024

  37. [45]

    Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

    Hugo Jacob and Marcin Pilipczuk . Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. InMichael A. Bekos and Michael Kaufmann , eds., Proc. 48th Int’l Workshop on Graph-Theoretic Concepts in Comput. Sci.(WG 2022), vol. 13453 of Lecture Notes ...

    2022

  38. [46]

    The density of fan-planar graphs.Electron

    Michael Kaufmann and Torsten Ueckerdt . The density of fan-planar graphs.Electron. J. Combin., 29(1), 2022

    2022

  39. [47]

    Simple treewidth

    Kolja Knauer and Torsten Ueckerdt . Simple treewidth. InPa vel Rytír, ed.,Midsummer Combinatorial Workshop Prague. 2012

    2012

  40. [48]

    A note on planar partial 3-trees

    Jan Kratochvíl and Michal V aner . A note on planar partial 3-trees. arXiv:1210.8113, 2012

    2012 arXiv

  41. [49]

    Twin-width of graphs on surfaces

    Daniel Kráľ, Kristýna Pekárkov á, and Kenny Štorgel . Twin-width of graphs on surfaces. In Rastisla v Královič and Antonín Kučera, eds.,Proc. 49th Int’l Symp. on Math’l Foundations of Comput. Sci.(MFCS 2024), vol. 306 ofLIPIcs, pp. 66:1–66:15. Schloss Dagstuhl, 2024

    2024

  42. [50]

    Paciornik

    Lilian Markenzon, Claudia Marcela Justel, and N. Paciornik . Subclasses of k-trees: characterization and recognition.Discrete Appl. Math., 154(5):818–825, 2006

    2006

  43. [51]

    Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997

    János Pach and Géza Tóth . Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997

    1997

  44. [52]

    Bruce A. Reed . Tree width and tangles: a new connectivity measure and some applications. In R. A. Bailey , ed.,Surveys in Combinatorics, vol. 241 ofLondon Math. Soc. Lecture Note Ser., pp. 87–162. Cambridge Univ. Press, 1997

    1997

  45. [53]

    Tree-partite graphs and the complexity of algorithms

    Detlef Seese. Tree-partite graphs and the complexity of algorithms. InLothar Budach, ed., Proc. Int’l Conf. on Fundamentals of Computation Theory, vol. 199 ofLecture Notes Comput. Sci., pp. 412–421. Springer, 1985

    1985

  46. [54]

    Graph searching and a min-max theorem for tree-width

    Paul Seymour and Robin Thomas . Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B, 58(1):22–33, 1993

    1993

  47. [55]

    New representation results for planar graphs

    F arhad Shahrokhi. New representation results for planar graphs. In29th European Workshop on Computational Geometry(EuroCG 2013), pp. 177–180. 2013. arXiv:1502.06175

    2013 arXiv

  48. [56]

    Wood, and Wendy Yi

    Torsten Ueckerdt, Da vid R. Wood, and Wendy Yi . An improved planar graph product structure theorem. Electron. J. Combin., 29:P2.51, 2022. 20

    2022

  49. [57]

    Geometrie der lage

    Karl Georg Christian von Staudt . Geometrie der lage. Verlag von Bauer and Rapse 25. Julius Merz, Nürnberg, 1847

  50. [58]

    Da vid R. Wood. Vertex partitions of chordal graphs.J. Graph Theory, 53(2):167–172, 2006

    2006

  51. [59]

    Da vid R. Wood. On tree-partition-width.European J. Combin., 30(5):1245–1253, 2009

    2009

  52. [60]

    Stacked treewidth and the Colin de Verdiére number

    Lasse Wulf. Stacked treewidth and the Colin de Verdiére number. 2016. Bachelorthesis, Institute of Theoretical Computer Science, Karlsruhe Institute of Technology. 21

    2016

Pith tools

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