Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

In this paper, we study collective additive tree spanners for families of graphs enjoying special Robertson-Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. We say that a graph G admits a system of @m collective additive tree r-spanners (resp., multiplicative tree t-spanners) if there is a system T(G) of at most @m spanning trees of G such that for any two vertices x,y of G a spanning tree T@?T(G) exists such that d"T(x,y)@?d"G(x,y)+r (resp., d"T(x,y)@?t@?d"G(x,y)). When @m=1 one gets the notion of additive tree r-spanner (resp., multiplicative tree t-spanner). It is known that if a graph G has a multiplicative tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most @?t/2@? in G. We use this to demonstrate that there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner, constructs a system of at most log"2n collective additive tree O(tlogn)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can ''turn'' a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result by showing that if a graph G admits a multiplicative t-spanner with tree-width k-1, then G admits a Robertson-Seymour's tree-decomposition each bag of which can be covered with at most k disks of G of radius at most @?t/2@? each. This is used to demonstrate that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k-1, constructs a system of at most k(1+log"2n) collective additive tree O(tlogn)-spanners of G.