TY - JOUR

T1 - Bounded-Diameter Tree-Decompositions

AU - Berger, Eli

AU - Seymour, Paul

N1 - Publisher Copyright:
© The Author(s), under exclusive licence to János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature 2024.

PY - 2024

Y1 - 2024

N2 - When does a graph admit a tree-decomposition in which every bag has small diameter? For finite graphs, this is a property of interest in algorithmic graph theory, where it is called having bounded “tree-length”. We will show that this is equivalent to being “boundedly quasi-isometric to a tree”, which for infinite graphs is a much-studied property from metric geometry. One object of this paper is to tie these two areas together. We will prove that there is a tree-decomposition in which each bag has small diameter, if and only if there is a map ϕ from V(G) into the vertex set of a tree T, such that for all u,v∈V(G), the distances dG(u,v),dT(ϕ(u),ϕ(v)) differ by at most a constant. A necessary condition for admitting such a tree-decomposition is that there is no long geodesic cycle, and for graphs of bounded tree-width, Diestel and Müller showed that this is also sufficient. But it is not sufficient in general, even qualitatively, because there are graphs in which every geodesic cycle has length at most three, and yet every tree-decomposition has a bag with large diameter. There is a more general necessary condition, however. A “geodesic loaded cycle” in G is a pair (C, F), where C is a cycle of G and F⊆E(C), such that for every pair u, v of vertices of C, one of the paths of C between u, v contains at most dG(u,v)F-edges, where dG(u,v) is the distance between u, v in G. We will show that a (possibly infinite) graph G admits a tree-decomposition in which every bag has small diameter, if and only if |F| is small for every geodesic loaded cycle (C, F). Our proof is an extension of an algorithm to approximate tree-length in finite graphs by Dourisboure and Gavoille. In metric geometry, there is a similar theorem that characterizes when a graph is quasi-isometric to a tree, “Manning’s bottleneck criterion”. The goal of this paper is to tie all these concepts together, and add a few more related ideas. For instance, we prove a conjecture of Rose McCarty, that G admits a tree-decomposition in which every bag has small diameter, if and only if for all vertices u, v, w of G, some ball of small radius meets every path joining two of u, v, w.

AB - When does a graph admit a tree-decomposition in which every bag has small diameter? For finite graphs, this is a property of interest in algorithmic graph theory, where it is called having bounded “tree-length”. We will show that this is equivalent to being “boundedly quasi-isometric to a tree”, which for infinite graphs is a much-studied property from metric geometry. One object of this paper is to tie these two areas together. We will prove that there is a tree-decomposition in which each bag has small diameter, if and only if there is a map ϕ from V(G) into the vertex set of a tree T, such that for all u,v∈V(G), the distances dG(u,v),dT(ϕ(u),ϕ(v)) differ by at most a constant. A necessary condition for admitting such a tree-decomposition is that there is no long geodesic cycle, and for graphs of bounded tree-width, Diestel and Müller showed that this is also sufficient. But it is not sufficient in general, even qualitatively, because there are graphs in which every geodesic cycle has length at most three, and yet every tree-decomposition has a bag with large diameter. There is a more general necessary condition, however. A “geodesic loaded cycle” in G is a pair (C, F), where C is a cycle of G and F⊆E(C), such that for every pair u, v of vertices of C, one of the paths of C between u, v contains at most dG(u,v)F-edges, where dG(u,v) is the distance between u, v in G. We will show that a (possibly infinite) graph G admits a tree-decomposition in which every bag has small diameter, if and only if |F| is small for every geodesic loaded cycle (C, F). Our proof is an extension of an algorithm to approximate tree-length in finite graphs by Dourisboure and Gavoille. In metric geometry, there is a similar theorem that characterizes when a graph is quasi-isometric to a tree, “Manning’s bottleneck criterion”. The goal of this paper is to tie all these concepts together, and add a few more related ideas. For instance, we prove a conjecture of Rose McCarty, that G admits a tree-decomposition in which every bag has small diameter, if and only if for all vertices u, v, w of G, some ball of small radius meets every path joining two of u, v, w.

KW - 05C10

KW - 05C62

KW - Geodesic

KW - Quasi-isometry

KW - Tree-decomposition

KW - Tree-length

UR - http://www.scopus.com/inward/record.url?scp=85189835770&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85189835770&partnerID=8YFLogxK

U2 - 10.1007/s00493-024-00088-1

DO - 10.1007/s00493-024-00088-1

M3 - Article

AN - SCOPUS:85189835770

SN - 0209-9683

JO - Combinatorica

JF - Combinatorica

ER -