2025/12/26 by Marc Distel, Distel, Marc
Mathematics · #Advanced Operator Algebra Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2512.21946
openalex publication_date 2025/12/26 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
Quasi-isometry is a measure of how similar two graphs are at `large-scale'. Nguyen, Scott, and Seymour [arXiv:2501.09839] and Hickingbotham [arXiv:2501.10840] independently gave a characterisation of graphs quasi-isometric to graphs of treewidth k. In this paper, we give a new characterisation of such graphs. Specifically, we show that such graphs G are characterised by the existence of a partition whose quotient has treewidth at most k and such that each part has bounded weak diameter in G. The primary contribution of our characterisation is a structural description of graphs that admit such a quasi-isometry. This differs from the characterisation mentioned above, which primarily shows the existence of such a quasi-isometry. The characterisations are complementary, and neither immediately implies the other.