Plane Embeddings of Planar Graph Metrics |
| |
Authors: | MohammadHossein Bateni Erik D Demaine MohammadTaghi Hajiaghayi Mohammad Moharrami |
| |
Institution: | (1) Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran;(2) Computer Science and Artificial Intelligence Laboratory, MIT, 32 Vassar St., Cambridge, MA 02139, USA;(3) Department of Computer Science, Carnegie Mellon University, 4109 Wean Hall, Pittsburgh, PA 15213, USA |
| |
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
distortion in the worst case M1], BMMV], 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 Matousek M3] by proving
that some planar graph metrics require
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
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
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|