Geodesic
Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002 , Tome 8 (2004) no. 2, pp. 135-160.

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

Trees are usually drawn planar, i.e. without any edge-crossings. In this paper, we investigate the area requirement of (non-upward) planar straight-line grid drawings of binary trees. Let T be a binary tree with n nodes. We show that T admits a planar straight-line grid drawing with area O(n) and with any pre-specified aspect ratio in the range [n−ε,nε], where ε is any constant, such that 0 ε 1. We also show that such a drawing can be constructed in O(nlogn) time. In particular, our result shows that optimal area (equal to O(n)) and optimal aspect ratio (equal to 1) are simultaneously achievable for such drawings. 
@article{JGAA_2004_8_2_a1,
     author = {Ashim Garg and Adrian Rusu},
     title = {Straight-line {Drawings} of {Binary} {Trees} with {Linear} {Area} and {Arbitrary} {Aspect} {Ratio}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {135--160},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2004},
     doi = {10.7155/jgaa.00086},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00086/}
}
TY  - JOUR
AU  - Ashim Garg
AU  - Adrian Rusu
TI  - Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 135
EP  - 160
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00086/
DO  - 10.7155/jgaa.00086
LA  - en
ID  - JGAA_2004_8_2_a1
ER  - 
%0 Journal Article
%A Ashim Garg
%A Adrian Rusu
%T Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
%J Journal of Graph Algorithms and Applications
%D 2004
%P 135-160
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00086/
%R 10.7155/jgaa.00086
%G en
%F JGAA_2004_8_2_a1
Ashim Garg; Adrian Rusu. Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
					, Tome 8 (2004) no. 2, pp. 135-160. doi : 10.7155/jgaa.00086. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00086/

Cité par Sources :