Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition

Lipp, Fabian and Wolff, Alexander and Zink, Johannes (2015) Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 52-59 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_5).

Full text not available from this repository.

Abstract

The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs as they compute a quadratic number of forces in each iteration. We speed up this computation by using an approximation based on the well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime—even on graphs with less then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths).

Item Type:Conference Paper
Classifications:M Methods > M.400 Force-directed / Energy-based
ID Code:1477

Repository Staff Only: item control page

References

Barnes, J., Hut, P.: A hierarchical O(NlogN) force-calculation algorithm. Nature 324(6096), 446–449 (1986)

Bartel, G., Gutwenger, C., Klein, K., Mutzel, P.: An experimental evaluation of multilevel layout methods. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 80–91. Springer, Heidelberg (2011)

Brandenburg, F.J., Himsolt, M., Rohrer, C.: An experimental comparison of force-directed and randomized graph drawing algorithms. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 76–87. Springer, Heidelberg (1996)

Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42(1), 67–90 (1995)

Eades, P.: A heuristics for graph drawing. Congr. Numerantium 42, 146–160 (1984)

Eppstein, D., Wang, J.Y.: A steady state model for graph power laws. In: 2nd International Workshop Web Dynamics (2002). http://​arxiv.​org/​abs/​cs/​0204001

Fink, M., Haverkort, H., Nöllenburg, M., Roberts, M., Schuhmann, J., Wolff, A.: Drawing metro maps using Bézier curves. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 463–474. Springer, Heidelberg (2013)

Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995)

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exp. 21(11), 1129–1164 (1991)

Gronemann, M.: Engineering the fast-multipole-multilevel method for multicore and SIMD architectures. Master’s thesis, Department of Computer Science, TU Dortmund (2009)

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005)

JUNG: Java Universal Network/Graph Framework. http://​jung.​sourceforge.​net. Accessed 2 September 2015

Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, New York, NY, USA (2007)

Rome Graphs. http://​graphdrawing.​org/​data.​html, http://​www.​graphdrawing.​org/​download/​rome-graphml.​tgz. Accessed 2 September 2015

Walshaw, C.: A multilevel algorithm for force-directed graph-drawing. J. Graph Algorithms Appl. 7(3), 253–285 (2003)