plane embeddings of planar graph metrics
Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires ?(? n ) distortion in the worst case [19, 1], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matouek [21] by proving that some planar graph metrics require ?( n 2/3 ) distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require ?( n ) distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with O(?n) distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.
planar graphs euclidean plane metric embedding