Babilon, Robert and Matousek, Jirí and Maxová, Jana and Valtr, Pavel (2002) Low-Distortion Embeddings of Trees. [Conference Paper]
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(\sqrt n)$; that is, we construct a mapping $f\:V\to{{\mathbf{R}}}^2$ such that $\rho(u,v)\leq \Vert f(u)-f(v)\Vert\leq O(\sqrt n)\cdot\rho(u,v)$ for every $u,v\in V$, where $\rho(u,v)$ denotes the length of the path from $u$ to $v$ 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 |
|---|---|
| Classifications: | G Algorithms and Complexity > G.490 Embeddings M Methods > M.900 Tree |
| ID Code: | 516 |
| Deposited By: | Arnopolina, Galina |
| Deposited On: | 22 Dec 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=343 |
Repository Staff Only: item control page
