Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github.
翻译:从计算机文件系统和动态呼唤图到假新闻传播和疾病传播,许多现实生活中都会出现变化中的树木,从计算机文件系统和动态呼唤图到假新闻传播和疾病传播,大多数静态树的布局算法在不断演变的环境中效果不佳(例如,在设计时序之间并不稳定)。动态图形布局算法更适合这项任务,尽管它们往往引入不必要的边缘交叉点。铭记这一点,我们提出两种方法来直观不断演变的树木,以保证没有边缘交叉点,同时优化(1) 理想边缘长度的实现,(2) 布局紧凑和(3) 稳定性。我们用量化指标(压力、理想边缘长度的实现、布局紧凑性、稳定性和运行时间)来评估现实世界数据集的两种新方法,以及先前的五种方法(三种静态和两种动态方法),我们用定量指标来评估这些新方法:压力、预期的边缘长度、布局紧凑性、稳定性和运行时间。新方法在 Githhub 上完全可以使用。