On Balloon Drawings of Rooted Trees

Lin, Chun-Cheng and Yen, Hsu-Chun (2006) On Balloon Drawings of Rooted Trees. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 285-296 (Official URL: http://dx.doi.org/10.1007/11618058_26).

Full text not available from this repository.


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. The radius of each circle is proportional to the number of descendents associated with the root node of the subtree. In this paper, we investigate various issues related to balloon drawing of rooted trees from both algorithmic and practical viewpoints. First, we design an efficient algorithm to optimize angular resolution and aspect ratio for the balloon drawing 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. Aside from studying balloon drawing from an algorithmic viewpoint, we also propose a local magnetic spring model (which can be thought of as a variant of the popular force-directed strategies) for producing dynamic balloon drawings for rooted trees. In our framework, each edge is modelled by a magnetized spring, while each vertex is placed on a local polar magnetic field which does not interact with other magnetic fields. Our approach facilitates various operations, including interaction and navigation, on trees. With a slight modification to our force-directed based balloon drawing algorithm, we are able to apply our work to the drawing of galaxy systems, H-trees, and sparse graphs, which are of practical interest.

Item Type:Conference Paper
Additional Information:10.1007/11618058_26
Classifications:M Methods > M.900 Tree
P Styles > P.999 Others
ID Code:698

Repository Staff Only: item control page


J. Carriere and R. Kazman.: Reserch report: Interacting with huge hierarchies: Beyond cone trees. IV 95, pages 74--81. IEEE CS Press, 1995.

P. Eades.: A heuristic for graph drawing. Congress Numerantium, 42:149--160, 1984.

C. S. Jeong and A. Pang.: Reconfigurable disc trees for visualizing large hierarchical information space. InfoVis '98, pages 19--25. IEEE CS Press, 1998.

H. Koike and H. Yoshihara.: Fractal approaches for visualizing huge hierarchies. VL '93, pages 55--60. IEEE CS Press, 1993.

J. Lamping, R. Rao, and P. Pirolli.: A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. CHI '95, pages 401--408. ACM Press, 1995.

G. Melancon and I. Herman.: Circular drawing of rooted trees. Reports of the Centre for Mathematics and Computer Sciences. Report number INS-9817, available at: http://www.cwi.nl/InfoVis/papers/circular.pdf, 1998.

C. H. Papadimitriou and K. Steiglitz.: Combinatorial optimization. Prentice Hall, Englewood Cliffs, New Jersey, 1982.

E. Reingold and J. Tilford.: Tidier drawing of trees. IEEE Trans. Software Eng., SE-7(2):223--228, 1981.

G. Robertson, J. Mackinlay, and S. Card.: Cone trees: Animated 3d visualizations of hierarchical information, human factors in computing systems. CHI '91, pages 189--194. ACM Press, 1991.

Y. Shiloach.: Arrangements of planar graphs on the planar lattices. Ph D Thesis, Weizmann Instite of Science, Rehovot, Israel, 1976.

K. Sugiyama and K. Misue.: Graph drawing by the magnetic spring model. J. Vis. Lang. Comput., 6:217--231, 1995.