Low-Distortion Embeddings of Trees

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 → R 2 such that \( \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.