Tree tt-spanners in outerplanar graphs via supply demand partition

A tree  tt-spanner   of an unweighted graph GG is a spanning tree TT such that for every two vertices their distance in TT is at most tt times their distance in GG. Given an unweighted graph GG and a positive integer tt as input, the Treett-spanner problem is to compute a tree tt-spanner of GG if one exists. This decision problem is known to be NP-complete even in the restricted class of unweighted planar graphs. We present a linear-time reduction from Treett-spanner in outerplanar graphs to the supply–demand tree partition problem. Based on this reduction, we obtain a linear-time algorithm to solve Treett-spanner in outerplanar graphs. Consequently, we show that the minimum value of tt for which an input outerplanar graph on nn vertices has a tree tt-spanner can be found in O(nlogn)O(nlogn) time.