Geodesic
On Balloon Drawings of Rooted Trees
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Thirteenth International Symposium on Graph Drawing, GD 2005 , Tome 11 (2007) no. 2, pp. 431-452.

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

Among various styles of tree drawing reported in the literature, balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. Each subtree in the balloon drawing of a tree is enclosed in a circle. Along any path from the root node, the radius of each circle reflects the number of descendants associated with the root node of the subtree. In this paper, we investigate various issues related to balloon drawings of rooted trees from the algorithmic viewpoint. First, we design an efficient algorithm to optimize the angular resolution and the aspect ratio for the balloon drawings of rooted unordered trees. For the case of ordered trees for which the center of the enclosing circle of a subtree need not coincide with the root of the subtree, flipping the drawing of a subtree (along the axis from the parent to the root of the subtree) might change both the aspect ratio and the angular resolution of the drawing. We show that optimizing the angular resolution as well as the aspect ratio with respect to this type of rooted ordered trees is reducible to the perfect matching problem for bipartite graphs, which is solvable in polynomial time. In addition, a related problem concerning the optimization of the drawing area can be modelled as a specific type of nonlinear programming for which there exist several robust algorithms in practice. With a slight modification to the balloon drawing, we are able to generate the drawings of galaxy systems, H-trees, and sparse graphs, which are of practical interest. 
@article{JGAA_2007_11_2_a5,
     author = {Chun-Cheng Lin and Hsu-Chun Yen},
     title = {On {Balloon} {Drawings} of {Rooted} {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {431--452},
     publisher = {mathdoc},
     volume = {11},
     number = {2},
     year = {2007},
     doi = {10.7155/jgaa.00153},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00153/}
}
TY  - JOUR
AU  - Chun-Cheng Lin
AU  - Hsu-Chun Yen
TI  - On Balloon Drawings of Rooted Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 431
EP  - 452
VL  - 11
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00153/
DO  - 10.7155/jgaa.00153
LA  - en
ID  - JGAA_2007_11_2_a5
ER  - 
%0 Journal Article
%A Chun-Cheng Lin
%A Hsu-Chun Yen
%T On Balloon Drawings of Rooted Trees
%J Journal of Graph Algorithms and Applications
%D 2007
%P 431-452
%V 11
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00153/
%R 10.7155/jgaa.00153
%G en
%F JGAA_2007_11_2_a5
Chun-Cheng Lin; Hsu-Chun Yen. On Balloon Drawings of Rooted Trees. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Thirteenth International Symposium on Graph Drawing, GD 2005
					, Tome 11 (2007) no. 2, pp. 431-452. doi : 10.7155/jgaa.00153. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00153/

Cité par Sources :