Tree-decompositions with bags of small diameter Original Research Article

This paper deals with the length of a Robertson–Seymourʹs tree-decomposition. The tree-length of a graph is the largest distance between two vertices of a bag of a tree-decomposition, minimized over all tree-decompositions of the graph. The study of this invariant may be interesting in its own right because the class of bounded tree-length graphs includes (but is not reduced to) bounded chordality graphs (like interval graphs, permutation graphs, AT-free graphs, etc.). For instance, we show that the tree-length of any outerplanar graph is image, where k is the chordality of the graph, and we compute the tree-length of meshes. More fundamentally we show that any algorithm computing a tree-decomposition approximating the tree-width (or the tree-length) of an n-vertex graph by a factor image or less does not give an image-approximation of the tree-length (resp. the tree-width) unless if image. We complete these results presenting several polynomial time constant approximate algorithms for the tree-length. The introduction of this parameter is motivated by the design of compact distance labeling, compact routing tables with near-optimal route length, and by the construction of sparse additive spanners.