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:
V →
R
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.