View Related Documents

Abstract

We prove that every tree T=(V, E) on n vertices can be embedded in the plane with distortion $ O(\sqrt n )$ O(\sqrt n ) that is, we construct a mapping f: VR 2 such that $ \rho (u,\upsilon ) \leqslant \parallel f(u) - f(\upsilon )\parallel \leqslant O(\sqrt n ) \cdot \rho (u,\upsilon )$ \rho (u,\upsilon ) \leqslant \parallel f(u) - f(\upsilon )\parallel \leqslant O(\sqrt n ) \cdot \rho (u,\upsilon ) for every u, υV, where ρ(u, υ) denotes the length of the path from u 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.
The research was supported by project LN00A056 of the Ministry of Education of the Czech Republic and by Charles University grants No.158/99 and 159/99.

Fulltext Preview

Image of the first page of the fulltext document