Journal of Graph Algorithms and Applications on Balloon Drawings of Rooted Trees
Journal of Graph Algorithms and Applications on Balloon Drawings of Rooted Trees
复制标题
有根树气球图的图算法与应用杂志
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
H. Yen
中科院分区：
文献类型：
--
作者：
Chun;H. Yen;P. Healy;Peter Eades;C. Lin;H. Yen
在文献报道的各种树木绘画风格中，气球绘画具有以相当平衡的方式展示树木结构的可取特征。树的引出序号图形中的每一棵子树都包围在一个圆中。沿着从根节点开始的任何路径，每个圆的半径反映与子树的根节点相关联的后代的数量。在本文中，我们从算法的角度研究了与根树的气球图相关的各种问题。首先，我们设计了一种高效的算法来优化有根无序树的气球图的角度分辨率和纵横比。对于子树的封闭圆的中心不必与子树的根重合的有序树的情况，翻转子树的图形(沿子树的父轴到子树根的轴)可能会更改图形的纵横比和角度分辨率。我们证明了对这类有根有序树的角度分辨率和纵横比的优化可以归结为二部图的完美匹配问题，该问题在多项式时间内是可解的。此外，与绘图区域优化有关的问题可以被建模为一类特定类型的非线性规划，对于该规划，在实践中有几种稳健的算法。对气球图稍作修改，我们就能生成有实际意义的星系图、H树图和稀疏图。
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.