SubLinearForce: Fully Sublinear-Time Force Computation for Large Complex Graph Drawing

Amyra Meidiana, Seok-Hee Hong, Shijun Cai, Marnijati Torkel, Peter Eades

Abstract

Recent works in graph visualization attempt to reduce the runtime of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">repulsion</i> force computation of force-directed algorithms using sampling. However, they fail to reduce the runtime for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">attraction</i> force computation to sublinear in the number of edges. We present the <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SubLinearForce</monospace> framework for a fully sublinear-time <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">force computation</i> algorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">attraction force</i> computation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.
BibTeX
@article{meidiana2024sublinearforce,
  author = {Amyra Meidiana and Seok-Hee Hong and Shijun Cai and Marnijati Torkel and Peter Eades},
  title = {{SubLinearForce: Fully Sublinear-Time Force Computation for Large Complex Graph Drawing}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2024},
  doi = {10.1109/tvcg.2022.3233287},
}

Loading related content...

Figure