Bounded diameter tree-decompositions

MaRDI QIDQ6510712arXivFDO

Authors Eli Berger, Paul Seymour

Published in arXiv

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83)

Abstract: When does a graph $G$ admit a tree-decomposition in which every bag has diameter at most $d$? One necessary condition is that there is no ``geodesic cycle of length more than $3d$; but this is not sufficient, even qualitatively, because one can make graphs in which every geodesic cycle has length at most four, and yet every tree-decomposition has a bag with large diameter. But there is a more general necessary condition. A ``geodesic loaded cycle in $G$ is a pair $(C,F)$, where $C$ is a cycle of $G$ and $FsubseteqE(C)$, such that for every pair $u,v$ of vertices of $C$, one of the paths of $C$ between $u,v$ contains at most $d_G(u,v)$ $F$-edges, where $d_G(u,v)$ is the distance between $u,v$ in $G$. We will show that $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)$. Admitting a tree-decomposition with bags of bounded diameter is known as having ``bounded tree-length in algorithmic graph theory, and our proof of the theorem above is similar to an algorithm to approximate tree-length by Dourisboure and Gavoille. Also, admitting such a tree-decomposition turns out to be equivalent to a popular property from metrical geometry, being ``boundedly quasi-isometric to a tree, and our theorem above about geodesic loaded cycles is essentially a rediscovery of Manning's theorem in metric space theory. 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$.

This page was built for publication: Bounded diameter tree-decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510712)