On Balloon Drawings of Rooted Trees
Resource
Journal of Graph Algorithms and Applications 11 (2): 431-452
Journal
Journal of Graph Algorithms and Applications
Journal Volume
11
Journal Issue
2
Pages
431-452
Date Issued
2007
Date
2007
Author(s)
Eades, Peter
Healy, Patrick
Abstract
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 draw- ings of galaxy systems, H-trees, and sparse graphs, which are of practical interest.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
23.pdf
Size
731.76 KB
Format
Adobe PDF
Checksum
(MD5):88a462d6a0918329d482380955696b9d