k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees (Extended Abstract)
Yuval Emek · 2009
Low distortion probabilistic embedding of graphs into ap- proximating trees is an extensively studied topic. Of particular interest is the case where the approximating trees are required to be (subgraph) spanning trees of the given graph (or multigraph), in which case, the focus is usually on the equivalent problem of finding a (single) tree with low average stretch. Among the classes of graphs that received special at- tention in this context arek-outerplanar graphs (for a fixed k): Chekuri, Gupta, Newman, Rabinovich, and Sinclair show that every k-outerplanar graph can be probabilistically embedded into approximating trees with constant distortion regardless of the size of the graph. The approximat- ing trees in the technique of Chekuri et al. are not necessarily spanning trees, though. In this paper it is shown that every k-outerplanar multigraph admits a spanning tree with constant average stretch. This immediately translates to a constant bound on the distortion of probabilistically embedding k- outerplanar graphs into their spanning trees. Moreover, a randomized algorithm is presented for constructing such a low average stretch span- ning tree in expected linear time. This algorithm relies on some new insights regarding the connection between low average stretch spanning trees and planar duality.