## Low-Distortion Embeddings of Trees
Babilon, Robert and Matousek, Jirí and Maxová, Jana and Valtr, Pavel
(2002)
Full text not available from this repository. ## AbstractWe 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 References |