Abstract.
The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions.
The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n 1 +O(1/r) edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received September 26, 1995, and in revised form March 18, 1996.
Rights and permissions
About this article
Cite this article
Rabinovich, Y., Raz, R. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete Comput Geom 19, 79–94 (1998). https://doi.org/10.1007/PL00009336
Issue Date:
DOI: https://doi.org/10.1007/PL00009336