Untangling Force-Directed Layouts Using Persistent Homology
Untangling Force-Directed Layouts Using Persistent Homology
复制标题
DOI：
10.1109/topoinvis57755.2022.00015
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Bhavana Doppalapudi;Bei Wang;P. Rosen
中科院分区：
文献类型：
--
作者：
Bhavana Doppalapudi;Bei Wang;P. Rosen
力导向布局属于一种用于在节点链接图中定位节点的流行方法。然而，它们通常缺乏对全局结构的直接考虑，这可能导致视觉混乱和不相关结构的重叠。在本文中，我们使用持久同源性的原则来解开力导向布局，从而减轻这些问题。首先，我们设计了一种新的方法，使用0维持久同源有效地产生一个初始的图形布局。该方法导致更快的收敛和更好的图形布局质量。其次，我们提供了一个新的定义和一个有效的算法，1维持久同源特征（即，隧道/循环）。我们为用户提供了与一维特征交互的能力，通过突出显示它们并向布局中添加强调循环的力量。最后，我们通过计算各种指标，例如，联合排名、边缘交叉等，以证明我们提出的方法的有效性。
Force-directed layouts belong to a popular class of methods used to position nodes in a node-link diagram. However, they typically lack direct consideration of global structures, which can result in visual clutter and the overlap of unrelated structures. In this paper, we use the principles of persistent homology to untangle force-directed layouts thus mitigating these issues. First, we devise a new method to use 0-dimensional persistent homology to efficiently generate an initial graph layout. The approach results in faster convergence and better quality graph layouts. Second, we provide a new definition and an efficient algorithm for 1-dimensional persistent homology features (i.e., tunnels/cycles) on graphs. We provide users the ability to interact with the 1-dimensional features by highlighting them and adding cycle-emphasizing forces to the layout. Finally, we evaluate our approach with 32 synthetic and real-world graphs by computing various metrics, e.g., co-ranking, edge crossing, etc., to demonstrate the efficacy of our proposed method.