REVIEW 3 cited by
Graphs that are quasi-isometric to graphs with bounded treewidth
Not yet reviewed by Pith; the record is open.
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
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.
Forward citations
Cited by 3 Pith papers
-
Asymptotic structure. III. Excluding a fat tree
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.
-
Optimal tree-decompositions with bags of bounded pathwidth
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.
-
A coarse block-cut tree theorem
Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.
Discussion (0). Continue with ORCID to comment.