Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00076 Low-Distortion Embeddings of Trees Robert Babilon , Jirí Matoušek , Jana Maxová , and Pavel Valtr Vol. 7, no. 4, pp. 399-409, 2003. Regular paper Abstract We prove that every tree T=(V,E) on n vertices with edges of unit length can be embedded in the plane with distortion O(√n); that is, we construct a mapping f V→R2 such that ρ(u,v) ≤ ||f(u)−f(v)|| ≤ O(√n)·ρ(u,v) for every u,v ∈ V, where ρ(u,v) denotes the length of the path from u to v in T. The embedding is described by a simple and easily computable formula. This is asymptotically optimal in the worst case. We also construct interesting optimal embeddings for a special class of trees (fans consisting of paths of the same length glued together at a common vertex).
|
Revised: April 2003. Submitted: May 2002. Communicated by Petra Mutzel and Michael Jünger |
| Journal of Graph Algorithms and Applications |