Spanners for bounded tree-length graphs

摘要

This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most delta, i.e., the tree-length delta graphs. For such graphs we construct additive 2 delta-spanners with O(delta n+n log n) edges, and additive 4 delta-spanners with O(delta n) edges. This provides new upper bounds for chordal graphs for which delta = 1. We also show a lower bound, and prove that there are graphs of tree-length delta for which every multiplicative delta-spanner (and thus every additive (delta - 1)-spanner) requires Omega(n(1+1/Theta(delta))) edges. (c) 2007 Elsevier B.V. All rights reserved.