Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Thirteenth International Symposium on Graph Drawing, GD 2005
DOI: 10.7155/jgaa.00153
On Balloon Drawings of Rooted Trees
Vol. 11, no. 2, pp. 431-452, 2007. Regular paper.
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 drawings of galaxy systems,
H-trees, and sparse graphs, which are of practical interest.
|
Journal Supporters
|