A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space

Abstract.

We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than

$\Omega(\sqrt{\log n})$

. This matches Rao's [14] general upper bound for metric embedding of planar graphs into Euclidean space, thus resolving the question how well do planar metrics embed in Euclidean spaces?

Similar content being viewed by others

Low distortion embeddings of some metric graphs into Banach spaces

Article 08 May 2017

Metric embeddings of Laakso graphs into Banach spaces

Article 26 August 2022

On metric dimension of plane graphs with \(\frac{m}{2}\) number of 10 sided faces

Article 28 August 2022

Author information

Authors and Affiliations

1. Computer Science Department, University of Haifa, Haifa 31905, Israel ilan@cs.haifa.ac.il, yuri@cs.haifa.ac.il, , , , , , IL

   Ilan Newman & Yuri Rabinovich

Authors

1. Ilan Newman
   View author publications

   You can also search for this author in PubMed Google Scholar

2. Yuri Rabinovich
   View author publications

   You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Newman, I., Rabinovich, Y. A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space . Discrete Comput Geom 29, 77–81 (2002). https://doi.org/10.1007/s00454-002-2813-5

Download citation

• Issue Date: December 2002

• DOI: https://doi.org/10.1007/s00454-002-2813-5

Keywords

• Euclidean Space
• Planar Graph
• Infinite Family
• Planar Metrics
• Embed Planar