SubLinearForce: Fully Sublinear-Time Force Computation for Large Complex Graph Drawing
Amyra Meidiana, Seok-Hee Hong, Shijun Cai, Marnijati Torkel, Peter Eades · IEEE Transactions on Visualization and Computer Graphics · 2023
Recent works in graph visualization attempt to reduce the runtime ofrepulsionforce computation of force-directed algorithms using sampling. However, they fail to reduce the runtime forattractionforce computation to sublinear in the number of edges. We present theSubLinearForceframework for a fully sublinear-timeforce computationalgorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for theattraction forcecomputation 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.