Untangling Force-Directed Layouts Using Persistent Homology

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.

Bhavana Doppalapudi, Bei Wang, and Paul Rosen. Untangling Force-Directed Layouts Using Persistent Homology. Topological Data Analysis and Visualization (TopoInVis), 2022.

@article{doppalapudi2022untangle,
  title = {Untangling Force-Directed Layouts Using Persistent Homology},
  author = {Doppalapudi, Bhavana and Wang, Bei and Rosen, Paul},
  journal = {Topological Data Analysis and Visualization (TopoInVis)},
  year = {2022},
  abstract = {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.}
}