Home | Issues | About JGAA | Instructions for Authors |
Advances in Graph Drawing. Special Issue on Selected Papers from
the Ninth International Symposium on Graph Drawing, GD 2001
DOI: 10.7155/jgaa.00076
Low-Distortion Embeddings of Trees
Vol. 7, no. 4, pp. 399-409, 2003. Regular paper.
Abstract We prove that every tree T=(V,E) on n vertices with edges of unit length
can be embedded in the plane with distortion O(√n);
that is, we construct a mapping f V→R2 such that
ρ(u,v) ≤ ||f(u)−f(v)|| ≤ O(√n)·ρ(u,v)
for every u,v ∈ V,
where ρ(u,v) denotes the length of the path from u to v
in T. The embedding
is described by a simple and easily computable
formula. This is asymptotically
optimal in the worst case. We also construct interesting optimal embeddings
for a special class of trees (fans consisting of paths of the same length
glued together at a common vertex).
|
Journal Supporters
|