Abstract: We first revisit the algorithm for computing the well-separated pair decomposition in time O(n log n). Then we show how this algorithm can be used to give a faster approximation to the Fruchterman-Reingold algorithm for force-directed graph drawing. Finally, we provide experimental evidence that this does not affect the quality of the results.
Paper by F. Lipp, A. Wolff and J. Zink from Graph Drawing 2015.