caa a22 4500 445805145 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9423-z doi (NATIONALLICENCE)springer-10.1007/s00453-010-9423-z Emek Yuval Microsoft Israel R&D Center, Herzelia, Israel aut k -Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees [Elektronische Daten] [Yuval Emek] Low distortion probabilistic embedding of graphs into approximating 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 attention in this context are k-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 approximating 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, an efficient randomized algorithm is presented for constructing such a low average stretch spanning tree. This algorithm relies on some new insights regarding the connection between low average stretch spanning trees and planar duality. Springer Science+Business Media, LLC, 2010 Planar graphs nationallicence Outerplanarity nationallicence Average stretch nationallicence Planar dual nationallicence Algorithmica Springer-Verlag 61/1(2011-09-01), 141-160 0178-4617 61:1<141 2011 61 453 https://doi.org/10.1007/s00453-010-9423-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9423-z text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Emek Yuval Microsoft Israel R&D Center, Herzelia, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 141-160 0178-4617 61:1<141 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer