Visual Computing

University of Konstanz
IEEE Transactions on Visualization and Computer Graphics

Force-Directed Graph Layouts Revisited: A New Force Based on the T-Distribution

F. Zhong, M. Xue, J. Zhang, F. Zhang, R. Ban, O. Deussen, Y. Wang
Teaser of Force-Directed Graph Layouts Revisited: A New Force Based on the T-Distribution

Abstract

In this paper, we propose the t-FDP model, a force-directed placement method based on a novel bounded short-range force (t-force) defined by Student’s t-distribution. Our formulation is flexible, exerts limited repulsive forces for nearby nodes and can be adapted separately in its short- and long-range effects. Using such forces in force-directed graph layouts yields better neighborhood preservation than current methods, while maintaining low stress errors. Our efficient implementation using a Fast Fourier Transform is one order of magnitude faster than state-of-the-art methods and two orders faster on the GPU, enabling us to perform parameter tuning by globally and locally adjusting the t-force in real-time for complex graphs. We demonstrate the quality of our approach by numerical evaluation against state-of-the-art approaches and extensions for interactive exploration.

BibTeX

@article{Zhong2023ForceDirectedGraph,
  author    = {F. Zhong, M. Xue, J. Zhang, F. Zhang, R. Ban, O. Deussen, Y. Wang},
  doi       = {10.1109/tvcg.2023.3238821},
  journal   = {IEEE Transactions on Visualization and Computer Graphics},
  pages     = {1--14},
  publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
  title     = {Force-Directed Graph Layouts Revisited: A New Force Based on the T-Distribution},
  year      = {2023}
}