Fast Node Overlap Removal

Dwyer, Tim and Marriott, Kim and Stuckey, Peter J. (2006) Fast Node Overlap Removal. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 153-164 (Official URL: http://dx.doi.org/10.1007/11618058_15).

WarningThere is a more recent version of this item available.

Full text not available from this repository.

Abstract

Most graph layout algorithms treat nodes as points. The problem of node overlap removal is to adjust the layout generated by such 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 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.

Item Type:Conference Paper
Additional Information:10.1007/11618058_15
Classifications:G Algorithms and Complexity > G.560 Geometry
ID Code:688

Available Versions of this Item

Repository Staff Only: item control page

References

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

Harel, D., Koren, Y.: Drawing graphs with non-uniform vertices. Proceedings of the Working Conference on Advanced Visual Interfaces (AVI'02), ACM Press (2002) 157-166

Friedrich, C., Schreiber, F.: Flexible layering in hierarchical drawings with nodes of arbitrary size. Proceedings of the 27th conference on Australasian computer science (ACSC2004). Volume 26., Australian Computer Society (2004) 369-376

Marriott, K., Moulder, P., Hope, L., Twardy, C.: Layout of bayesian networks. Twenty-Eighth Australasian Computer Science Conference (ACSC2005). Volume 38 of CRPIT., Australian Computer Society (2005) 97-106

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages and Computing 6 (1995) 183-210

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

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. GD '98: Proceedings of the 6th International Symposium on Graph Drawing, London, UK, Springer-Verlag (1998) 183-197

Lai, W., Eades, P.: Removing edge-node intersections in drawings of graphs. Inf. Process. Lett. 81 (2002) 105-110

Gansner, E.R., North, S.C.: Improved force-directed layouts. In: GD '98: Proceedings of the 6th International Symposium on Graph Drawing, London, UK, Springer-Verlag (1998) 364-373

Lyons, K.A.: Cluster busting in anchored graph drawing. CASCON '92: Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, IBM Press (1992) 327-337

Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. Proceedings of the Asia-Pacific Symposium on Information Visualisation (APVIS2005). Volume 45 of CRPIT., Australian Computer Society (2005) 131-140

Preparata, F.P., Shamos, M.I.: Computational Geometry. Springer (1985), 359-365

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 (1999)

Fletcher, R.: Practical Methods of Optimization. Chichester: John Wiley Inc. (1987)

ApS, M.: (Mosek optimisation toolkit v3.2) www.mosek.com