A Scalable Method for Readable Tree Layouts
A Scalable Method for Readable Tree Layouts
复制标题
DOI：
10.1109/tvcg.2023.3274572
复制
发表时间：
2023-05
影响因子：
5.2
通讯作者：
Kathryn E. Gray;Mingwei Li;R. Ahmed;Md. Khaledur Rahman;A. Azad;S. Kobourov;K. Börner
中科院分区：
文献类型：
--
作者：
Kathryn E. Gray;Mingwei Li;R. Ahmed;Md. Khaledur Rahman;A. Azad;S. Kobourov;K. Börner
大型树结构是普遍存在的，并且真实世界的关系数据集通常具有与节点相关联的信息（例如，标签或其它属性）和边（例如，权重或距离），这些信息需要传达给观众。然而，可扩展的，易于阅读的树型布局很难实现。如果树布局满足一些基本要求，我们认为它们是可读的：节点标签不应该重叠，边缘不应该交叉，边缘长度应该保持不变，输出应该紧凑。有许多算法用于绘制树，尽管很少考虑节点标签或边长度，并且没有一个优化上述所有要求。考虑到这一点，我们提出了一个新的可扩展的方法可读的树布局。该算法保证布局没有边缘交叉和标签重叠，并优化其余方面之一：所需的边缘长度和紧凑性。我们通过与使用几个真实世界数据集（从几千个节点到几十万个节点）的相关早期方法进行比较来评估新算法的性能。树布局算法可用于通过提取逐渐变大的树的层次来可视化大型通用图。我们通过展示几个由新的树布局算法生成的类似地图的可视化来说明此功能。
Large tree structures are ubiquitous and real-world relational datasets often have information associated with nodes (e.g., labels or other attributes) and edges (e.g., weights or distances) that need to be communicated to the viewers. Yet, scalable, easy to read tree layouts are difficult to achieve. We consider tree layouts to be readable if they meet some basic requirements: node labels should not overlap, edges should not cross, edge lengths should be preserved, and the output should be compact. There are many algorithms for drawing trees, although very few take node labels or edge lengths into account, and none optimizes all requirements above. With this in mind, we propose a new scalable method for readable tree layouts. The algorithm guarantees that the layout has no edge crossings and no label overlaps, and optimizes one of the remaining aspects: desired edge lengths and compactness. We evaluate the performance of the new algorithm by comparison with related earlier approaches using several real-world datasets, ranging from a few thousand nodes to hundreds of thousands of nodes. Tree layout algorithms can be used to visualize large general graphs, by extracting a hierarchy of progressively larger trees. We illustrate this functionality by presenting several map-like visualizations generated by the new tree layout algorithm.