TY - JOUR
T1 - Complexity analysis of balloon drawing for rooted trees
AU - Lin, Chun Cheng
AU - Yen, Hsu Chun
AU - Poon, Sheung Hung
AU - Fan, Jia Hao
N1 - Funding Information:
The authors thank the anonymous referees for their comments that greatly improved the quality as well as the presentation of the paper. The second author (Hsu-Chun Yen) was supported in part by the Institute for Information Industry, Taiwan, under the project ‘‘Next Generation Telematics Systems and Innovative Applications/Services Technologies’’.
PY - 2011/2/4
Y1 - 2011/2/4
N2 - In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general.
AB - In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general.
KW - Graph algorithms
KW - Graph drawing
KW - Tree drawing
UR - http://www.scopus.com/inward/record.url?scp=78650844255&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2010.10.015
DO - 10.1016/j.tcs.2010.10.015
M3 - Article
AN - SCOPUS:78650844255
SN - 0304-3975
VL - 412
SP - 430
EP - 447
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 4-5
ER -