Dwyer, Tim and Marriott, Kim and Stuckey, Peter J. (2006) Fast Node Overlap Removal. [Conference Paper]
 | There is a more recent version of this eprint available. Click here to view it. |
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 |
|---|---|
| Classifications: | G Algorithms and Complexity > G.999 Others |
| ID Code: | 688 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 22 Feb 2006 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3843&spage=153 |
Available Versions of this Item
- Fast Node Overlap Removal. (deposited 22 Feb 2006) [Currently Displayed]
Repository Staff Only: item control page
