TY - GEN

T1 - On balloon drawings of rooted trees

AU - Lin, Chun-Cheng

AU - Yen, Hsu Chun

PY - 2006

Y1 - 2006

N2 - Among various styles of tree drawing, balloon drawing, where each subtree is enclosed in a circle, enjoys a desirable feature of displaying tree structures in a rather balanced fashion. We first 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 for producing dynamic balloon drawings with applications to the drawings of galaxy systems, H-trees, and sparse graphs, which are of practical interest.

AB - Among various styles of tree drawing, balloon drawing, where each subtree is enclosed in a circle, enjoys a desirable feature of displaying tree structures in a rather balanced fashion. We first 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 for producing dynamic balloon drawings with applications to the drawings of galaxy systems, H-trees, and sparse graphs, which are of practical interest.

UR - http://www.scopus.com/inward/record.url?scp=33745644055&partnerID=8YFLogxK

U2 - 10.1007/11618058_26

DO - 10.1007/11618058_26

M3 - Conference contribution

AN - SCOPUS:33745644055

SN - 3540314253

SN - 9783540314257

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 285

EP - 296

BT - Graph Drawing - 13th International Symposium, GD 2005, Revised Papers

T2 - 13th International Symposium on Graph Drawing, GD 2005

Y2 - 12 September 2005 through 14 September 2005

ER -