{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:29:28Z","timestamp":1760441368036,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T00:00:00Z","timestamp":1470268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 give a new algorithm that takes only     O ( m + n log n )     time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called 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 than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).<\/jats:p>","DOI":"10.3390\/a9030053","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:17:33Z","timestamp":1470305853000},"page":"53","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-0454","authenticated-orcid":false,"given":"Fabian","family":"Lipp","sequence":"first","affiliation":[{"name":"Lehrstuhl f\u00fcr Informatik I, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Informatik I, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Zink","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Informatik I, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,8,4]]},"reference":[{"key":"ref_1","first-page":"146","article-title":"A heuristics for graph drawing","volume":"42","author":"Eades","year":"1984","journal-title":"Congr. Numerantium"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1002\/spe.4380211102","article-title":"Graph drawing by force-directed placement","volume":"21","author":"Fruchterman","year":"1991","journal-title":"Softw. Pract. Exp."},{"key":"ref_3","unstructured":"Fink, M., Haverkort, H., N\u00f6llenburg, M., Roberts, M., Schuhmann, J., and Wolff, A. (2013). Graph Drawing, Springer."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1038\/324446a0","article-title":"A hierarchical O(N log N) force-calculation algorithm","volume":"324","author":"Barnes","year":"1986","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"253","DOI":"10.7155\/jgaa.00070","article-title":"A Multilevel Algorithm for Force-Directed Graph-Drawing","volume":"7","author":"Walshaw","year":"2003","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_6","unstructured":"Hachul, S., and J\u00fcnger, M. (2005). Graph Drawing, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0021-9991(87)90140-9","article-title":"A fast algorithm for particle simulations","volume":"73","author":"Greengard","year":"1987","journal-title":"J. Comput. Phys."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Hachul, S. (2005). A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. [Ph.D. Thesis, Universit\u00e4t zu K\u00f6ln].","DOI":"10.1007\/978-3-540-31843-9_29"},{"key":"ref_9","unstructured":"Godiyal, A., Hoberock, J., Garland, M., and Hart, J.C. (2009). Graph Drawing, Springer."},{"key":"ref_10","unstructured":"Bartel, G., Gutwenger, C., Klein, K., and Mutzel, P. (2011). Graph Drawing, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Brandenburg, F.J., Himsolt, M., and Rohrer, C. (1996). Graph Drawing, Springer.","DOI":"10.1007\/BFb0021783"},{"key":"ref_12","unstructured":"Frick, A., Ludwig, A., and Mehldau, H. (1995). Graph Drawing, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","article-title":"A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields","volume":"42","author":"Callahan","year":"1995","journal-title":"J. ACM"},{"key":"ref_14","unstructured":"Gronemann, M. (2009). Engineering the Fast-Multipole-Multilevel Method for Multicore and SIMD Architectures. [Master\u2019s Thesis, Technical University of Dortmund]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.jvlc.2011.12.002","article-title":"Improving multiple aesthetics produces better graph drawings","volume":"24","author":"Huang","year":"2013","journal-title":"J. Vis. Lang. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.jvlc.2011.12.001","article-title":"A new force-directed graph drawing method based on edge\u2013edge repulsion","volume":"23","author":"Lin","year":"2012","journal-title":"J. Vis. Lang. Comput."},{"key":"ref_17","first-page":"37","article-title":"Efficient, High-Quality Force-Directed Graph Drawing","volume":"10","author":"Hu","year":"2006","journal-title":"Math. J."},{"key":"ref_18","unstructured":"O\u2019Madadhain, J., Fisher, D., and White, S. Java Universal Network\/Graph Framework (JUNG). Available online: http:\/\/jung.sourceforge.net."},{"key":"ref_19","unstructured":"Chimani, M., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Klein, K., and Mutzel, P. (2014). Handbook of Graph Drawing and Visualization, CRC Press."},{"key":"ref_20","unstructured":"Lipp, F., Wolff, A., and Zink, J. Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Available online: http:\/\/www1.pub.informatik.uni-wuerzburg.de\/pub\/data\/frwspd\/."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Narasimhan, G., and Smid, M. (2007). Geometric Spanner Networks, Cambridge University Press.","DOI":"10.1017\/CBO9780511546884"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"345","DOI":"10.7155\/jgaa.00150","article-title":"Large-Graph Layout Algorithms at Work: An Experimental Study","volume":"11","author":"Hachul","year":"2007","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_23","unstructured":"Rome Graphs. Available online: http:\/\/graphdrawing.org\/data.html."},{"key":"ref_24","unstructured":"North, S. North Graphs. Available online: http:\/\/graphdrawing.org\/data.html."},{"key":"ref_25","unstructured":"Eppstein, D., and Wang, J.Y. (2002, January 7). A steady state model for graph power laws. Proceedings of the 2nd International Workshop on Web Dynamics, Honolulu, HI, USA."},{"key":"ref_26","unstructured":"Rumsey, D.J. (2009). Statistics II for Dummies, Wiley Publishing."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/53\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:27:43Z","timestamp":1760210863000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,4]]},"references-count":26,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["a9030053"],"URL":"https:\/\/doi.org\/10.3390\/a9030053","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,8,4]]}}}