Top

previous chapter A Sparse Stress Model

next chapter Placing Arrows in Directed Graph Drawings

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Node Overlap Removal by Growing a Tree

Read first chapter

Authors: Lev Nachmanson, Arlind Nocaj, Sergey Bereg, Leishi Zhang, Alexander Holroyd

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

Node overlap removal is a necessary step in many scenarios including laying out a graph, or visualizing a tag cloud. Our contribution is a new overlap removal algorithm that iteratively builds a Minimum Spanning Tree on a Delaunay triangulation of the node centers and removes the node overlaps by “growing” the tree. The algorithm is simple to implement yet produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

http://www.graphviz.org/.

https://github.com/Microsoft/automatic-graph-layout.

http://www.graphviz.org.

https://www.dropbox.com/sh/4q0k89yrv4x3ae3/AAA3xyKFRhLyyHXcG9jpcgata?dl=0.

Borg, I., Groenen, P.: Modern Multidimensional Scaling: Theory and Applications. Springer, New York (2005) MATH

Dwyer, T., Koren, Y., Marriott, K.: IPSEP-COLA: an incremental procedure for separation constraint layout of graphs. IEEE Trans. Vis. Comput. Graph. 12(5), 821–828 (2006) CrossRef

Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: Healy, P., Nikolov, N.S. (eds.) GD 2006. LNCS, pp. 153–164. Springer, Heidelberg (2006). doi: 10.1007/11618058_15 CrossRef

Friedrich, C., Schreiber, F.: Flexible layering in hierarchical drawings with nodes of arbitrary size. In: Estivill-Castro, V., (ed.), ACSC, vol. 26, CRPIT, pp. 369–376. Australian Computer Society (2004)

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

Gansner, E.R., Hu, Y.: Efficient, proximity-preserving node overlap removal. J. Graph Algorithms Appl. 14(1), 53–74 (2010) MathSciNetCrossRefMATH

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2004) CrossRef

Gansner, E.R., North, S.C.: Improved force-directed layouts. In: Whitesides, S. (ed.) GD 1998. LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1998) CrossRef

Gomez-Nieto, E., Casaca, W., Nonato, L.G., Taubin, G.: Mixed integer optimization for layout arrangement. In: 2013 26th SIBGRAPI-Conference on Graphics, Patterns and Images (SIBGRAPI), pp. 115–122. IEEE (2013)

10.

Gomez-Nieto, E., San Roman, F., Pagliosa, P., Casaca, W., Helou, E., de Oliveira, M.F., Nonato, L.: Similarity preserving snippet-based visualization of web search results. IEEE Trans. Vis. Comput. Graph. 20, 457–470 (2013) CrossRef

11.

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. Syst. Comput. Japan 33(2), 31–42 (2002) CrossRef

12.

Hu, Y.: Visualizing graphs with node and edge labels. CoRR, abs/0911.0626 (2009)

13.

Huang, X., Lai, W.: Force-transfer: a new approach to removing overlapping nodes in graph layout. In: Oudshoorn, M.J. (ed.), ACSC, vol. 16, CRPIT, pp. 349–358. Australian Computer Society (2003)

14.

Huang, X., Lai, W., Sajeev, A., Gao, J.: A new algorithm for removing node overlapping in graph visualization. Inf. Sci. 177(14), 2821–2844 (2007) MathSciNetCrossRefMATH

15.

Imamichi, T., Arahori, Y., Gim, J., Hong, S.-H., Nagamochi, H.: Removing node overlaps using multi-sphere scheme. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 296–301. Springer, Heidelberg (2008). doi: 10.1007/978-3-642-00219-9_28 CrossRef

16.

Li, W., Eades, P., Nikolov, N.S.: Using spring algorithms to remove node overlapping. In: Hong, S.-H. (ed.), APVIS, vol. 45, CRPIT, pp. 131–140. Australian Computer Society (2005)

17.

Lin, C.-C., Yen, H.-C., Chuang, J.-H.: Drawing graphs with nonuniform nodes using potential fields. J. Vis. Lang. Comput. 20(6), 385–402 (2009) CrossRef

18.

Lyons, K.A., Meijer, H., Rappaport, D.: Algorithms for cluster busting in anchored graph drawing. J. Graph Algorithms Appl. 2(1), 1–24 (1998) MathSciNetCrossRefMATH

19.

Marriott, K., Stuckey, P.J., Tam, V., He, W.: Removing node overlapping in graph layout using constrained optimization. Constraints 8(2), 143–171 (2003) MathSciNetCrossRefMATH

20.

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Vis. Lang. Comput. 6(2), 183–210 (1995) CrossRef

21.

Strobelt, H., Spicker, M., Stoffel, A., Keim, D., Deussen, O.: Rolled-out wordles: a heuristic method for overlap removal of 2d data representatives. In: Computer Graphics Forum, vol. 31, pp. 1135–1144. Wiley Online Library (2012)

22.

Strobelt, H., Spicker, M., Stoffel, A., Keim, D.A., Deussen, O.: Rolled-out wordles: a heuristic method for overlap removal of 2d data representatives. Comput. Graph. Forum 31(3), 1135–1144 (2012) CrossRef

23.

Tamassia, R.: Handbook of Graph Drawing and Visualization (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, Boca Raton (2007)

24.

Wang, X., Miyamoto, I.: Generating customized layouts. In: Brandenburg, F.-J. (ed.) GD 1995. LNCS, vol. 1027, pp. 504–515. Springer, Heidelberg (1995). doi: 10.1007/BFb0021835 CrossRef

Title

Node Overlap Removal by Growing a Tree

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_3

Authors:

Lev Nachmanson
Arlind Nocaj
Sergey Bereg
Leishi Zhang
Alexander Holroyd

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits