Low-Distortion Embeddings of Trees

Babilon, Robert and Matousek, Jirí and Maxová, Jana and Valtr, Pavel (2002) Low-Distortion Embeddings of Trees. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 343-351 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_27).

Full text not available from this repository.

Abstract

We prove that every tree T=(V, E) on n vertices can be embedded in the plane with distortion O(n); that is, we construct a mapping f: V → R 2 such that for every u, υ ∈ V, where ρ(u, υ) denotes the length of the path fromu to υ in T (the edges have unit lengths). The embedding is described by a simple and easily computable formula. This is asymptotically optimal in the worst case. We also prove several related results.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_27
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.900 Tree
ID Code:516

Repository Staff Only: item control page

References

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th Ann. IEEE Sympos. on foundations of Computer Science, pages 184-193, 1996.

U. Feige. Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci., 60:510-539, 2000.

A. Gupta. Embedding tree metrics into low dimensional Euclidean spaces. Discrete Comput. Geom., 24:105-116, 2000.

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), 215-245.

J. Matousek. Bi-Lipschitz embeddings into low dimensional Euclidean spaces. Comment. Math. Univ. Carolina, 31:589-600, 1990.

S. Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In. Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), ACM, New York, 1999, 300-306.