A spanning tree T of a graph G is called a tree
t‐spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n‐vertex m‐edge unweighted graph G:
a tree (2⌊log2
n⌋)‐spanner in O(mlogn) time, if G is a chordal graph (i.e., every induced cycle of G has length 3);
a tree (2ρ⌊log2
n⌋)‐spanner in O(mnlog2
n) time or a tree (12ρ⌊log2
n⌋)‐spanner in O(mlogn) time, if G is a graph admitting a Robertson‐Seymour’s tree‐decomposition with bags of radius at most ρ in G; and
a tree (2⌈t/2⌉⌊log2
n⌋)‐spanner in O(mnlog2
n) time or a tree (6t⌊log2
n⌋)‐spanner in O(mlogn) time, if G is an arbitrary graph admitting a tree t‐spanner.
For the latter result we use a new necessary condition for a graph to have a tree t‐spanner: if a graph G has a tree t‐spanner, then G admits a Robertson‐Seymour’s tree‐decomposition with bags of radius at most ⌈t/2⌉ and diameter at most t in G.
