Paper by Erik D. Demaine
- 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 Ω(n2/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.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.