## Fast Node Overlap Removal
Dwyer, Tim and Marriott, Kim and Stuckey, Peter J.
(2006)
Full text not available from this repository. ## AbstractMost 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.
## Available Versions of this Item-
Fast Node Overlap Removal. (deposited 22 Feb 2006)
**[Currently Displayed]**
Repository Staff Only: item control page References |