**Reference**:- MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Mohammad Moharrami, “Plane Embeddings of Planar Graph Metrics”, in
*Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006)*, Sedona, Arizona, June 5–7, 2006, pages 197–206. **Abstract**:-
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 Matoušek [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. **Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (397k), gzipped PostScript (138k), and PDF (204k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PlaneEmbedding_DCG (Plane Embeddings of Planar Graph Metrics)

See also other papers by Erik Demaine.

Last updated March 12, 2024 by Erik Demaine.