Abstract
The problem of node overlap removal is to adjust the layout generated by typical graph drawing methods so that nodes of non-zero width and height do not overlap, yet are as close as possible to their original positions. We give an O(n log n) algorithm for achieving this assuming that the number of nodes overlapping any single node is bounded by some constant. This method has two parts, a constraint generation algorithm which generates a linear number of “separation” constraints and an algorithm for finding a solution to these constraints “close” to the original node placement values. We also extend our constraint solving algorithm to give an active set based algorithm which is guaranteed to find the optimal solution but which has considerably worse theoretical complexity. We compare our method with convex quadratic optimization and force scan approaches and find that it is faster than either, gives results of better quality than force scan methods and similar quality to the quadratic optimisation approach.
Chapter PDF
Similar content being viewed by others
References
Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)
Harel, D., Koren, Y.: Drawing graphs with non-uniform vertices. In: Proceedings of the Working Conference on Advanced Visual Interfaces (AVI 2002), pp. 157–166. ACM Press, New York (2002)
Friedrich, C., Schreiber, F.: Flexible layering in hierarchical drawings with nodes of arbitrary size. In: Proceedings of the 27th conference on Australasian computer science (ACSC 2004), vol. 26, pp. 369–376. Australian Computer Society (2004)
Marriott, K., Moulder, P., Hope, L., Twardy, C.: Layout of bayesian networks. In: Twenty-Eighth Australasian Computer Science Conference (ACSC 2005). CRPIT, vol. 38, pp. 97–106. Australian Computer Society (2005)
Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages and Computing 6, 183–210 (1995)
Marriott, K., Stuckey, P., Tam, V., He, W.: Removing node overlapping in graph layout using constrained optimization. Constraints 8, 143–171 (2003)
Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 183–197. Springer, Heidelberg (1999)
Lai, W., Eades, P.: Removing edge-node intersections in drawings of graphs. Inf. Process. Lett. 81, 105–110 (2002)
Gansner, E.R., North, S.C.: Improved force-directed layouts. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1999)
Lyons, K.A.: Cluster busting in anchored graph drawing. In: CASCON 11992: Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, pp. 327–337. IBM Press (1992)
Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. In: Proceedings of the Asia-Pacific Symposium on Information Visualisation (APVIS 2005). CRPIT, vol. 45, pp. 131–140. Australian Computer Society (2005)
Preparata, F.P., Shamos, M.I.: Computational Geometry, pp. 359–365. Springer, Heidelberg (1985)
Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. Technical Report 2005/173, Monash University, School of Computer Science and Software Engineering (2005), Available from: www.csse.monash.edu.au/~tdwyer
Weiss, M.A.: Data Structures and Algorithm Analysis in Java. Addison-Wesley Longman, Amsterdam (1999)
Fletcher, R.: Practical Methods of Optimization. John Wiley & Sons, Inc., Chichester (1987)
ApS, M.: (Mosek optimisation toolkit v3.2), http://www.mosek.com
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwyer, T., Marriott, K., Stuckey, P.J. (2006). Fast Node Overlap Removal. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_15
Download citation
DOI: https://doi.org/10.1007/11618058_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)