https://scholars.lib.ntu.edu.tw/handle/123456789/155109
標題: | On Balloon Drawings of Rooted Trees | 作者: | Eades, Peter Healy, Patrick |
公開日期: | 2007 | 卷: | 11 | 期: | 2 | 起(迄)頁: | 431-452 | 來源出版物: | Journal of Graph Algorithms and Applications | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-67650513638&doi=10.7155%2fjgaa.00153&partnerID=40&md5=007f6393c06a5559843a19dfdbdc2f13 | DOI: | 10.7155/jgaa.00153 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。