Conference Proceedings

Fast node overlap removal

T Dwyer, K Marriott, PJ Stuckey, P Healy (ed.), NS Nikolov (ed.)

GRAPH DRAWING | SPRINGER-VERLAG BERLIN | Published : 2006

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 ..

View full abstract