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 , pp. 153-164(Official URL:

WarningThere is a more recent version of this item available.
Full text not available from this repository.


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

Available Versions of this Item

Actions (login required)

View Item View Item