Geodesic
Low-Distortion Embeddings of Trees
Journal of Graph Algorithms and Applications, Advances in Graph Drawing. Special Issue on Selected Papers from the Ninth International Symposium on Graph Drawing, GD 2001 , Tome 7 (2003) no. 4, pp. 399-409.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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). 
@article{JGAA_2003_7_4_a4,
     author = {Robert Babilon and Jir{\'\i} Matou\v{s}ek and Jana Maxov\'a and Pavel Valtr},
     title = {Low-Distortion {Embeddings} of {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {399--409},
     publisher = {mathdoc},
     volume = {7},
     number = {4},
     year = {2003},
     doi = {10.7155/jgaa.00076},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00076/}
}
TY  - JOUR
AU  - Robert Babilon
AU  - Jirí Matoušek
AU  - Jana Maxová
AU  - Pavel Valtr
TI  - Low-Distortion Embeddings of Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2003
SP  - 399
EP  - 409
VL  - 7
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00076/
DO  - 10.7155/jgaa.00076
LA  - en
ID  - JGAA_2003_7_4_a4
ER  - 
%0 Journal Article
%A Robert Babilon
%A Jirí Matoušek
%A Jana Maxová
%A Pavel Valtr
%T Low-Distortion Embeddings of Trees
%J Journal of Graph Algorithms and Applications
%D 2003
%P 399-409
%V 7
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00076/
%R 10.7155/jgaa.00076
%G en
%F JGAA_2003_7_4_a4
Robert Babilon; Jirí Matoušek; Jana Maxová; Pavel Valtr. Low-Distortion Embeddings of Trees. Journal of Graph Algorithms and Applications, 
							Advances in Graph Drawing. Special Issue on Selected Papers from
    the Ninth International Symposium on Graph Drawing, GD 2001
					, Tome 7 (2003) no. 4, pp. 399-409. doi : 10.7155/jgaa.00076. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00076/

Cité par Sources :