<Emphasis Type="Italic">k</Emphasis>-Outerplanar Graphs,Planar Duality,and Low Stretch Spanning Trees |
| |
Authors: | Yuval Emek |
| |
Affiliation: | 1.Microsoft Israel R&D Center,Herzelia,Israel;2.School of Electrical Engineering,Tel Aviv University,Tel Aviv,Israel |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|