Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008
Efficient, Proximity-Preserving Node Overlap Removal
Vol. 14, no. 1, pp. 53-74, 2010. Regular paper.
Abstract When drawing graphs whose nodes contain text or graphics, the non-trivial node sizes must be taken into account, either as part of the initial layout or as a post-processing step. The core problem in avoiding or removing overlaps is to retain the structural information inherent in a layout while minimizing the additional area required. This paper presents a new node overlap removal algorithm that does well at retaining a graph's shape while using little additional area and time. As part of the analysis, we consider and evaluate two measures of dissimilarity for two layouts of the same graph.
Submitted: November 2008.
Reviewed: March 2009.
Revised: May 2009.
Accepted: November 2009.
Final: November 2009.
Published: January 2010.
article (PDF)