On Balloon Drawings of Rooted Trees - Lin, Chun-Cheng; Yen, Hsu-Chun (Journal of Graph Algorithms and Applications, 2007)
Among various styles of tree drawing reported in the literature,balloon drawing enjoys a desirable feature of displayingtree structures in a rather balanced fashion. Each subtree in theballoon drawing of a tree is enclosed in a circle. <!----> Along any path from the root node, the radius of each circlereflects the number of descendants associated with the root node ofthe subtree. In this paper, we investigate various issues related toballoon drawings of rooted trees from the algorithmic viewpoint.First, we design an efficient algorithm to optimize the angularresolution and the aspect ratio for the balloon drawings of rootedunordered trees. For the case of ordered trees for which the centerof the enclosing circle of a subtree need not coincide with the rootof the subtree, flipping the drawing of a subtree (along the axisfrom the parent to the root of the subtree) might change both theaspect ratio and the angular resolution of the drawing. We show thatoptimizing the angular resolution as well as the aspect ratio withrespect to this type of rooted ordered trees is reducible to theperfect matching problem for bipartite graphs, which is solvable inpolynomial time. In addition, a related problem concerning theoptimization of the drawing area can be modelled as a specific typeof nonlinear programming for which there exist several robustalgorithms in practice. With a slight modification to the balloondrawing, we are able to generate the drawings of galaxy systems,H-trees, and sparse graphs, which are of practical interest. <!---->