Asymptotic structure. I. Coarse tree-width

Abstract

In this paper, we develop a coarse analogue of tree-width. We prove that a graph $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of balls of bounded radius, if and only if $G$ admits a quasi-isometry to a graph with bounded tree-width. (The ``if'' half is easy, but the ``only if'' half is challenging.) This generalizes a recent result of Berger and Seymour, concerning tree-decompositions when each bag has bounded radius. We also prove a similar result for line-width, which is an extension of path-width to infinite graphs.

arXiv commentv4: 22 pages, major revision