Node overlap removal algorithms: an extended comparative study. (English) Zbl 1451.05225

Summary: In the context of graph layout, many algorithms have been designed to remove node overlapping, and many quality criteria and associated metrics have been proposed to evaluate those algorithms. Unfortunately, a complete comparison of the algorithms based on some metrics that evaluate their quality has never been provided and it is thus difficult for a visualisation designer to select the algorithm that best suits their needs. In this paper, we review 22 metrics available in the literature, classify them according to the quality criteria they try to capture, and select a representative one for each class. Based on the selected metrics, we compare 9 node overlap removal algorithms. Our experiment involves 854 synthetic and real-world graphs. Finally, we propose a JavaScript library containing both the algorithms and the criteria, and we provide a Web platform, AGORA, in which one can upload graphs, apply the algorithms and compare/download the results.


05C85 Graph algorithms (graph-theoretic aspects)


JavaScript; AGORA; OGDF
Full Text: DOI


[1] D. W. Archambault and H. C. Purchase. The “map” in the mental map: Experimental results in dynamic graph drawing.International Journal of Human-Computer Studies, 71(11):1044-1055, 2013.
[2] A.-L. Baraba´si and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. · Zbl 1226.05223
[3] F. Chen, L. Piccinini, P. Poncelet, and A. Sallaberry. Node overlap removal algorithms: A comparative study. InProceedings of the International Symposium on Graph Drawing and Network Visualization (GD), pages 179-192. Springer, 2019. · Zbl 07266115
[4] M. Chimani, C. Gutwenger, M. J¨unger, G. W. Klau, K. Klein, and P. Mutzel. The open graph drawing framework (OGDF). In R. Tamassia, editor,Handbook on Graph Drawing and Visualization., pages 543-569. Chapman and Hall/CRC, 2013.
[5] T. Dwyer, K. Marriott, and P. J. Stuckey. Fast node overlap removal. InProceedings of the International Symposium on Graph Drawing (GD), pages 153-164. Springer, 2005. · Zbl 1171.68609
[6] P. Erd¨os and A. R´enyi. On random graphs.Publicationes Mathematicae Debrecen, 6:290-291, 1959.
[7] S. Fadloun, P. Poncelet, J. Rabatel, M. Roche, and A. Sallaberry. Node overlap removal for 1d graph layout. InProceeding of the International Conference on Information Visualisation (IV), pages 224 - 229, 2017.
[8] E. R. Gansner and Y. Hu. Efficient, proximity-preserving node overlap removal.Journal of Graph Algorithms and Applications, 14(1):53-74, 2010. · Zbl 1185.68778
[9] E. R. Gansner and S. C. North.An open graph visualization system and its applications to software engineering.Software: practice and experience, 30(11):1203-1233, 2000. · Zbl 1147.68782
[10] D. Guo and M. Gahegan. Spatial ordering and encoding for geographic data mining and visualization.Journal of Intelligent Information Systems, 27(3):243-266, 2006.
[11] S. Hachul and M. J¨unger. Drawing large graphs with a potential-fieldbased multilevel algorithm. InProceedings of the International Symposium on Graph Drawing (GD), pages 285-295. Springer, 2004.
[12] J. Haunert and L. Sering. Drawing road networks with focus regions.IEEE Transactions on Visualization and Computer Graphics, 17(12):2555-2562, 2011.
[13] K. Hayashi, M. Inoue, T. Masuzawa, and H. Fujiwara. A layout adjustment problem for disjoint rectangles preserving orthogonal order. InProceedings of the International Symposium on Graph Drawing (GD), pages 183-197. Springer, 1998.
[14] Y. Hu. Efficient, high-quality force-directed graph drawing.Mathematica Journal, 10(1):37-71, 2005.
[15] X. Huang and W. Lai. Force-transfer: a new approach to removing overlapping nodes in graph layout. InProceedings of the Australasian Computer Science Conference (ACSC), pages 349-358, 2003.
[16] X. Huang, W. Lai, A. Sajeev, and J. Gao.A new algorithm for removing node overlapping in graph visualization.Information Sciences, 177(14):2821 - 2844, 2007. · Zbl 1122.68144
[17] W. Li, P. Eades, and N. Nikolov. Using spring algorithms to remove node overlapping. InProceedings of the Asia-Pacific Symposium on Information Visualisation (APVis’05), pages 131-140, 2005.
[18] K. A. Lyons, H. Meijer, and D. Rappaport. Algorithms for cluster busting in anchored graph drawing.Journal of Graph Algorithms and Applications, 2(1):1-24, 1998. · Zbl 0892.68073
[19] K. Marriott, P. Stuckey, V. Tam, and W. He. Removing node overlapping in graph layout using constrained optimization.Constraints, 8(2):143-171, 2003. · Zbl 1039.68121
[20] W. Meulemans. Efficient optimal overlap removal: Algorithms and experiments.Computer Graphics Forum, 38(3):713-723, 2019.
[21] K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map.Journal of Visual Languages & Computing, 6(2):183-210, 1995.
[22] L. Nachmanson, A. Nocaj, S. Bereg, L. Zhang, and A. Holroyd. Node overlap removal by growing a tree. InProceedings of the International Symposium on Graph Drawing and Network Visualization (GD), pages 33- 43. Springer, 2016. · Zbl 1478.68255
[23] S. Nickel, M. Sondag, W. Meulemans, M. Chimani, S. G. Kobourov, J. Peltonen, and M. N¨ollenburg.Computing stable demers cartograms.In Proceedings of the International Symposium on Graph Drawing and Network Visualization (GD), pages 46-60. Springer, 2019. · Zbl 07266105
[24] H. C. Purchase. Metrics for graph drawing aesthetics.Journal of Visual Languages & Computing, 13(5):501-516, 2002.
[25] M. Sondag, B. Speckmann, and K. Verbeek.Stable treemaps via local moves.IEEE Transactions on Visualization and Computer Graphics, 24(1):729-738, 2018.
[26] H. Strobelt, M. Spicker, A. Stoffel, D. A. Keim, and O. Deussen. Rolledout wordles: A heuristic method for overlap removal of 2D data representatives.Computer Graphics Forum, 31(3):1135-1144, 2012.
[27] M. van Garderen, B. Pampel, A. Nocaj, and U. Brandes.Minimumdisplacement overlap removal for geo-referenced data visualization.Computer Graphics Forum, 36(3):423-433, 2017.
[28] D. · Zbl 1368.05139
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.