Pith. sign in

REVIEW 7 cited by

Graphs that are quasi-isometric to graphs with bounded treewidth

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2501.10840 v2 pith:EE7KQFTN submitted 2025-01-18 math.CO

Graphs that are quasi-isometric to graphs with bounded treewidth

Robert Hickingbotham This is my paper
classification math.CO
keywords graphsboundedquasi-isometrictreewidthcharacterisegraphnumberadditionally
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In this paper, we characterise graphs that are quasi-isometric to graphs with bounded treewidth. Specifically, we prove that a graph is quasi-isometric to a graph with bounded treewidth if and only if it has a tree-decomposition where each bag consists of a bounded number of balls of bounded diameter. This result extends a characterisation by Berger and Seymour (2024) of graphs that are quasi-isometric to trees. Additionally, we characterise graphs that are quasi-isometric to graphs with bounded pathwidth and graphs that are quasi-isometric to graphs with bounded linewidth. As an application of these results, we show that graphs with bounded rank-width, graphs with bounded tree independence number, and graphs with bounded sim-width are quasi-isometric to graphs with bounded treewidth.

discussion (0)

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

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Asymptotic structure. III. Excluding a fat tree

    math.CO 2025-09 conditional novelty 8.0

    Any graph lacking a c-fat tree minor can be quasi-isometrically approximated by a graph with line-width bounded in terms of the tree and c.

  2. Optimal tree-decompositions with bags of bounded pathwidth

    math.CO 2026-07 accept novelty 7.0

    Every planar graph admits an optimal tree-decomposition in which every bag induces a subgraph of pathwidth at most 3, with an O(k) bound on unions of k bags, and analogues for fixed-surface graphs.

  3. Vertex cuts and median decompositions

    math.CO 2026-06 unverdicted novelty 7.0

    Median decompositions arise from any system of vertex cuts via Sageev's dual median graph, are uniquely minimal, satisfy median-width equals clique number on all graphs, and characterize proper geometric actions of gr...

  4. Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs

    math.CO 2026-06 unverdicted novelty 7.0

    Verifies stronger coarse balanced separator conjecture for all r in K_{t,t}-induced-minor-free graphs of bounded clique number via a polynomial-size hitting set Z for large balls on any Y.

  5. A coarse Menger's Theorem for planar and bounded genus graphs

    math.CO 2026-05 unverdicted novelty 7.0

    In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.

  6. Coarse Menger property of quasi-minor excluded graphs and length spaces

    math.CO 2026-05 unverdicted novelty 7.0

    Locally finite graphs with an excluded finite minor have the weak coarse Menger property with f depending only on k and g linear in r independent of k.

  7. A coarse block-cut tree theorem

    math.CO 2026-07 accept novelty 6.0

    Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.