Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
A Sparse Stress Model
Mark Ortmann, Mirza Klimenta, and Ulrik Brandes
Vol. 21, no. 5, pp. 791-821, 2017. Regular paper.
Abstract Force-directed layout methods are among the most common approaches for drawing general graphs. Among them, stress minimization produces layouts of comparatively high quality while also imposing comparatively high computational demands. We propose a speed-up method based on the aggregation of terms in the objective function. It is akin to aggregate repulsion from far-away nodes during spring embedding but transfers the idea from the layout space into a preprocessing phase. An initial experimental study informs a method to select representatives, and subsequent more extensive experiments indicate that our method yields better approximations of minimum-stress layouts in less time than related methods.
Submitted: December 2016.
Reviewed: March 2017.
Revised: April 2017.
Reviewed: June 2017.
Revised: July 2017.
Accepted: July 2017.
Final: July 2017.
Published: October 2017.
Communicated by Yifan Hu and Martin Nöllenburg
article (PDF)