pith. sign in

arxiv: 2607.02098 · v1 · pith:4SFVKVCLnew · submitted 2026-07-02 · 🧮 math.CO · cs.DM· cs.DS

Separating Geodesic Structure and Product Structure

Laura Merker , Lena Scherzer , Samuel Schneider This is my paper

Pith reviewed 2026-07-03 10:33 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.DS
keywords geodesic treewidthrow treewidthtreewidthgraph contractionsNP-hardnessplanar graphsproduct structurelayerings
0
0 comments X

The pith

Geodesic treewidth and row treewidth are distinct parameters, with bounded row treewidth failing to imply bounded geodesic treewidth.

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

The paper separates geodesic treewidth from row treewidth by constructing graphs where row treewidth remains bounded but geodesic treewidth grows arbitrarily large. It supplies a polynomial-time algorithm that decides whether any treewidth-2 graph has geodesic treewidth exactly 1, while the same decision problem is NP-hard for row treewidth. The work also establishes that geodesic treewidth is NP-hard to compute in general, that geodesic treewidth 1 forces row treewidth to be bounded, and that every planar graph has geodesic treewidth at least 5.

Core claim

The geodesic treewidth of a graph G is the smallest k such that the vertices can be partitioned into geodesics whose contraction produces a graph of treewidth k. Row treewidth is the smallest k such that G is a subgraph of the strong product of a treewidth-k graph with a path, equivalently defined via partitions into aligned unions of geodesics. The authors prove these parameters are distinct by exhibiting graphs of bounded row treewidth with unbounded geodesic treewidth, while showing the converse direction holds for geodesic treewidth 1; they further separate the parameters computationally and raise the planar lower bound to 5.

What carries the argument

Partition of vertices into geodesics (or aligned unions of geodesics) whose contraction yields a graph of small treewidth, versus the strong-product definition with a path for row treewidth.

If this is right

  • There exist graphs with bounded row treewidth but arbitrarily large geodesic treewidth.
  • Deciding whether a treewidth-2 graph has geodesic treewidth 1 is solvable in polynomial time.
  • Deciding whether geodesic treewidth is at most d is solvable in time XP in the treewidth of the input graph.
  • Computing the exact geodesic treewidth of an arbitrary graph is NP-hard.
  • Every graph with geodesic treewidth 1 has row treewidth bounded by some constant independent of the graph.
  • The geodesic treewidth of every planar graph is at least 5.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The strong-product characterization with a path captures a weaker structural requirement than unrestricted geodesic partitions.
  • Techniques for geodesic partitions may apply to other contraction-based width measures that lack an alignment condition.
  • The separation raises the question of whether similar distinctions appear between geodesic treewidth and other product-based parameters such as layered treewidth.

Load-bearing premise

The stated equivalence between the product-structure definition and the aligned-layering partition definition of row treewidth holds for the graphs under consideration.

What would settle it

A concrete family of graphs with row treewidth bounded by some fixed constant k yet geodesic treewidth exceeding every fixed bound, or a counterexample showing the polynomial-time decision procedure for treewidth-2 graphs fails on some input.

Figures

Figures reproduced from arXiv: 2607.02098 by Laura Merker, Lena Scherzer, Samuel Schneider.

Figure 13
Figure 13. Figure 13: To verify that distances are preserved, recall that in [PITH_FULL_IMAGE:figures/full_fig_p014_13.png] view at source ↗
read the original abstract

The geodesic treewidth of a graph $ G $ is the smallest $k$ for which there is a partition $\mathcal{P}$ into geodesics such that $G/\mathcal{P}$ has treewidth $k$, where $G/\mathcal{P}$ is obtained from $ G $ by contracting each part of $ \mathcal{P} $. Based on this notion, row treewidth was developed and is defined for a graph $ G $ as the smallest $ k $ such that $ G \subseteq H \boxtimes P $ for some graph $ H $ of treewidth $ k $ and a path $ P $. Equivalently, the row treewidth of a graph $ G $ is the smallest $ k $ for which there is a partition $ \mathcal{P} $ into disjoint unions of geodesics that are aligned with respect to some layering such that $ G/\mathcal{P} $ has treewidth $ k $. We separate the two notions by showing that bounded row treewidth does not imply bounded geodesic treewidth and by presenting a polynomial-time algorithm to decide whether a graph of treewidth 2 has geodesic treewidth 1, which is known to be NP-hard for row treewidth [Biedl, Eppstein, Ueckerdt, 2025]. More generally, we provide an algorithm to decide whether a given graph has geodesic treewidth at most $ d $ that is XP in the treewidth, whereas there is no such algorithm for row treewidth, unless P = NP [Biedl, Eppstein, Ueckerdt, 2025]. On the other hand, we show that computing the geodesic treewidth is NP-hard and that every graph with geodesic treewidth 1 has bounded row treewidth. Moreover, we improve the best known lower bound on the geodesic treewidth of planar graphs to 5.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper defines geodesic treewidth of a graph G as the smallest k such that there exists a partition of V(G) into geodesics where the contraction G/P has treewidth k. Row treewidth is defined as the smallest k such that G is a subgraph of H ⊠ P for some graph H of treewidth k and path P, and equivalently via a partition into aligned disjoint unions of geodesics with respect to a layering such that the contraction has treewidth k. The central claims are that bounded row treewidth does not imply bounded geodesic treewidth; there is a polynomial-time algorithm to decide if a treewidth-2 graph has geodesic treewidth 1 (contrasting with NP-hardness for row treewidth); there is an XP algorithm (parameterized by treewidth) to decide if geodesic treewidth is at most d; computing geodesic treewidth is NP-hard; every graph of geodesic treewidth 1 has bounded row treewidth; and the geodesic treewidth of planar graphs is at least 5.

Significance. If correct, the results cleanly separate two related parameters, establishing that they differ both structurally (one does not bound the other in both directions) and computationally (different complexity behaviors under parameterization by treewidth). The explicit algorithmic contrast with prior row-treewidth hardness results and the improved planar lower bound are concrete advances in the study of product structures and layered decompositions. The paper supplies the requested equivalence verification between the product and aligned-layering definitions of row treewidth, so the stress-test concern does not land.

minor comments (2)
  1. [Introduction] Introduction: the statement that 'every graph with geodesic treewidth 1 has bounded row treewidth' should include an explicit bound or reference to the section deriving the constant.
  2. The citation to Biedl et al. (2025) for the row-treewidth hardness results should be updated if a published version or arXiv identifier is now available.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the results, and recommendation of minor revision. The equivalence verification between the product and aligned-layering definitions of row treewidth is already included, addressing the prior stress-test concern. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No circularity detected; all claims rest on explicit definitions, constructions, and external hardness results.

full rationale

The paper introduces geodesic treewidth via a partition into geodesics and row treewidth via both a product-structure definition and an equivalent aligned-layering partition definition. It then proves separations (bounded row tw does not imply bounded geodesic tw), algorithmic distinctions (poly-time for geodesic tw=1 on tw-2 graphs vs NP-hard for row tw), NP-hardness of computing geodesic tw, and a lower bound of 5 for planar graphs. These rest on direct constructions and reductions rather than any fitted parameters, self-definitional loops, or load-bearing self-citations. The cited hardness result is from unrelated authors (Biedl et al.), and the stated equivalence between row-tw definitions is used as a definitional bridge without reducing the separation theorems to it by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are identifiable from the provided text.

pith-pipeline@v0.9.1-grok · 5871 in / 1193 out tokens · 42270 ms · 2026-07-03T10:33:59.502884+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 25 canonical work pages

  1. [1]

    and Gronemann, Martin and Raftopoulou, Chrysanthi N

    Bekos, Michael A. and Gronemann, Martin and Raftopoulou, Chrysanthi N. , year =. An. Algorithmica , volume =

  2. [2]

    Notes on Graph Product Structure Theory

    Dvo r \'a k, Zden e k and Huynh, Tony and Joret, Gwenael and Liu, Chun-Hung and Wood, David R. Notes on Graph Product Structure Theory. 2019-20 MATRIX Annals. 2021. doi:10.1007/978-3-030-62497-2_32

    work page doi:10.1007/978-3-030-62497-2_32 2019

  3. [3]

    An efficient algorithm for

    Shinwoo An and Seonghyuk Im and Seokbeom Kim and Myounghwan Lee , year=. An efficient algorithm for. 2510.14674 , archivePrefix=

    work page arXiv

  4. [4]

    1998 , issn =

    Upper Bounds on the Size of Obstructions and Intertwines , journal =. 1998 , issn =. doi:https://doi.org/10.1006/jctb.1997.1788 , author =

    work page doi:10.1006/jctb.1997.1788 1998

  5. [5]

    Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Adler, Isolde and Grohe, Martin and Kreutzer, Stephan , title =. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2008 , publisher =

    2008

  6. [6]

    Combinatorica , volume=

    Neighborhood complexity of planar graphs , author=. Combinatorica , volume=. 2024 , publisher=

    2024

  7. [7]

    49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , pages =

    Kr\'. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.MFCS.2024.66 , annote =

    work page doi:10.4230/lipics.mfcs.2024.66 2024

  8. [8]

    Computing in Geometry and Topology , author=

    On the Complexity of Embedding in Graph Products , volume=. Computing in Geometry and Topology , author=. 2025 , month=. doi:10.57717/cgt.v4i2.56 , number=

    work page doi:10.57717/cgt.v4i2.56 2025

  9. [9]

    1984 , issn =

    A simplified NP-complete satisfiability problem , journal =. 1984 , issn =. doi:10.1016/0166-218X(84)90081-7 , author =

    work page doi:10.1016/0166-218x(84)90081-7 1984

  10. [10]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , year =

    Proof of the Clustered Hadwiger Conjecture , author =. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , year =

    2023

  11. [11]

    On Comparable Box Dimension , booktitle =

    Dvo. On Comparable Box Dimension , booktitle =. 2022 , volume =

    2022

  12. [12]

    Planar Graphs Have Bounded Queue-Number , year =

    Dujmovi\'. Planar Graphs Have Bounded Queue-Number , year =. doi:10.1145/3385731 , journal =

    work page doi:10.1145/3385731

  13. [13]

    and Yi, Wendy , journal =

    Ueckerdt, Torsten and Wood, David R. and Yi, Wendy , journal =. An Improved Planar Graph Product Structure Theorem , doi =

  14. [14]

    2023 , issn =

    Graph product structure for non-minor-closed classes , journal =. 2023 , issn =. doi:10.1016/j.jctb.2023.03.004 , author =

    work page doi:10.1016/j.jctb.2023.03.004 2023

  15. [15]

    SIAM Journal on Discrete Mathematics , author =

    Shorter. SIAM Journal on Discrete Mathematics , author =. 2022 , note =. doi:10.1137/20M1330464 , number =

    work page doi:10.1137/20m1330464 2022

  16. [16]

    Adjacency Labelling for Planar Graphs (and Beyond) , year =

    Dujmovi\'. Adjacency Labelling for Planar Graphs (and Beyond) , year =. doi:10.1145/3477542 , journal =

    work page doi:10.1145/3477542

  17. [17]

    Journal of the London Mathematical Society , volume =

    Esperet, Louis and Joret, Gwenaël and Morin, Pat , title =. Journal of the London Mathematical Society , volume =. doi:10.1112/jlms.12781 , year =

    work page doi:10.1112/jlms.12781

  18. [18]

    Planar graphs have bounded nonrepetitive chromatic number , journal =

    Vida Dujmovi. Planar graphs have bounded nonrepetitive chromatic number , journal =. doi:10.19086/aic.12100 , year = 2020, month =

    work page doi:10.19086/aic.12100 2020

  19. [19]

    2022 , primaryClass =

    Odd Colourings of Graph Products , author =. 2022 , primaryClass =

    2022

  20. [20]

    2021 , issn =

    Polynomial bounds for centered colorings on proper minor-closed graph classes , journal =. 2021 , issn =. doi:10.1016/j.jctb.2021.06.002 , author =

    work page doi:10.1016/j.jctb.2021.06.002 2021

  21. [21]

    Improved Bounds for Centered Colorings , journal =

    Micha. Improved Bounds for Centered Colorings , journal =. doi:10.19086/aic.27351 , year =

    work page doi:10.19086/aic.27351

  22. [22]

    Dujmović, Vida and Esperet, Louis and Morin, Pat and Walczak, Bartosz and Wood, David R. , year=. Clustered 3-colouring graphs of bounded degree , volume=. Combinatorics, Probability and Computing , publisher=. doi:10.1017/S0963548321000213 , number=

    work page doi:10.1017/s0963548321000213

  23. [23]

    2025 , publisher =

    Strong odd coloring in minor-closed classes , author=. 2025 , publisher =

    2025

  24. [24]

    2020 , copyright =

    Asymptotically Optimal Vertex Ranking of Planar Graphs , publisher =. 2020 , copyright =. doi:10.48550/ARXIV.2007.06455 , author =

    work page doi:10.48550/arxiv.2007.06455 2020

  25. [25]

    2025 , primaryClass=

    Structure of k -Matching-Planar Graphs , author=. 2025 , primaryClass=. doi:10.48550/arXiv.2507.22395 , publisher =

    work page doi:10.48550/arxiv.2507.22395 2025

  26. [26]

    2026 , issn =

    Reduced bandwidth: A qualitative strengthening of twin-width in minor-closed classes (and beyond) , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.jctb.2025.11.010 , author =

    work page doi:10.1016/j.jctb.2025.11.010 2026

  27. [27]

    , title =

    Hickingbotham, Robert and Wood, David R. , title =. SIAM Journal on Discrete Mathematics , volume =. 2024 , doi =

    2024

  28. [28]

    2017 , doi =

    Layered separators in minor-closed graph classes with applications , journal =. 2017 , doi =

    2017

  29. [29]

    Separating layered treewidth and row treewidth , journal =

    Prosenjit Bose and Vida Dujmovi. Separating layered treewidth and row treewidth , journal =. doi:10.46298/dmtcs.7458 , year = 2022, month =

    work page doi:10.46298/dmtcs.7458 2022

  30. [30]

    Powers of planar graphs, product structure, and blocking partitions , journal =

    Distel, Marc and Hickingbotham, Robert and Seweryn, Micha. Powers of planar graphs, product structure, and blocking partitions , journal =. 2024 , doi =

    2024

  31. [31]

    and Da Lozzo, Giordano and Hlin

    Bekos, Michael A. and Da Lozzo, Giordano and Hlin. Graph Product Structure for h-Framed Graphs , doi =. The Electronic Journal of Combinatorics , pages =

  32. [32]

    1998 , issn =

    A partial k-arboretum of graphs with bounded treewidth , journal =. 1998 , issn =. doi:10.1016/S0304-3975(97)00228-4 , author =

    work page doi:10.1016/s0304-3975(97)00228-4 1998

  33. [33]

    Pathwidth of pathwidth-bounded graphs

    Kloks, Ton. Pathwidth of pathwidth-bounded graphs. Treewidth: Computations and Approximations. 1994. doi:10.1007/BFb0045388

    work page doi:10.1007/bfb0045388 1994

  34. [34]

    18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) , pages =

    Bose, Prosenjit and Morin, Pat and Odak, Saeed , title =. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) , pages =. 2022 , volume =

    2022

  35. [35]

    Algorithmica , volume =

    Pat Morin , title =. Algorithmica , volume =. 2021 , doi =

    2021

  36. [36]

    42nd International Symposium on Computational Geometry (SoCG 2026) , pages =

    Bl\". 42nd International Symposium on Computational Geometry (SoCG 2026) , pages =. 2026 , volume =. doi:10.4230/LIPIcs.SoCG.2026.18 , annote =

    work page doi:10.4230/lipics.socg.2026.18 2026

  37. [37]

    , title =

    Hickingbotham, Robert and Jungeblut, Paul and Merker, Laura and Wood, David R. , title =. Journal of Graph Theory , volume =. doi:https://doi.org/10.1002/jgt.23008 , year =

    work page doi:10.1002/jgt.23008

  38. [38]

    1990 , issn =

    Forbidden minors characterization of partial 3-trees , journal =. 1990 , issn =. doi:10.1016/0012-365X(90)90292-P , author =

    work page doi:10.1016/0012-365x(90)90292-p 1990

  39. [39]

    and Tung, L

    Satyanarayana, A. and Tung, L. , title =. Networks , volume =. doi:10.1002/net.3230200304 , year =

    work page doi:10.1002/net.3230200304