Low-Distortion Embeddings of Trees

Babilon, Robert and Matoušek, Jiří and Maxová, Jana and Valtr, Pavel (2002) Low-Distortion Embeddings of Trees. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/516

Actions (login required)

View Item View Item