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.
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.
Repository Staff Only: item control page