Geodesic
Grid Drawings of Binary Trees: An Experimental Study
Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 2, pp. 131-195.

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

In this paper we consider the class of binary trees and present the results of a comprehensive experimental study on the four most representative algorithms for drawing trees, one for each of the following tree-drawing approaches: Separation-Based, Path-based, Level-based, and Ringed Circular Layout. We establish a simpler, more intuitive format for storing binary trees in files and create a large suite of randomly-generated, unbalanced, complete, AVL, Fibonacci, and molecular combinatory binary trees of various sizes. Our study is therefore conducted on randomly-generated, unbalanced, and AVL binary trees with between 100 and 50,000 nodes, on Fibonacci trees Tn for n=1,2,...,45,46 (143 to 46,367 nodes), on complete binary trees of size 2n−1 for n=7,8,...,15,16 (127 to 65,535 nodes), and on molecular combinatory binary trees with between 133 and 50,005 nodes. Our study yields 70 charts comparing the performance of the drawing algorithms with respect to ten quality measures, namely Area, Aspect Ratio, Size, Total Edge Length, Average Edge Length, Maximum Edge Length, Uniform Edge Length, Angular Resolution, Closest Leaf, and Farthest Leaf. None of the algorithms has been found to be the best in all categories. This observation leads us to create an adaptive system that determines the type of a binary tree and then selects an algorithm to draw the tree depending upon the specified quality measures. Currently, our adaptive tree drawing system recognizes all six types of binary trees and all ten measures included in our experimental study. Under our settings, our adaptive tree drawing system outperforms any system using a single binary tree drawing algorithm. 
@article{JGAA_2008_12_2_a0,
     author = {Adrian Rusu and Confesor Santiago},
     title = {Grid {Drawings} of {Binary} {Trees:} {An} {Experimental} {Study}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {131--195},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2008},
     doi = {10.7155/jgaa.00163},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00163/}
}
TY  - JOUR
AU  - Adrian Rusu
AU  - Confesor Santiago
TI  - Grid Drawings of Binary Trees: An Experimental Study
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 131
EP  - 195
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00163/
DO  - 10.7155/jgaa.00163
LA  - en
ID  - JGAA_2008_12_2_a0
ER  - 
%0 Journal Article
%A Adrian Rusu
%A Confesor Santiago
%T Grid Drawings of Binary Trees: An Experimental Study
%J Journal of Graph Algorithms and Applications
%D 2008
%P 131-195
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00163/
%R 10.7155/jgaa.00163
%G en
%F JGAA_2008_12_2_a0
Adrian Rusu; Confesor Santiago. Grid Drawings of Binary Trees: An Experimental Study. Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 2, pp. 131-195. doi : 10.7155/jgaa.00163. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00163/

Cité par Sources :