Node Overlap Removal by Growing a Tree
Lev Nachmanson, Arlind Nocaj, Sergey Bereg, Leishi Zhang, and Alexander Holroyd
Vol. 21, no. 5, pp. 857-872, 2017. Regular paper.
Abstract Node overlap removal is a necessary step in many scenarios including laying out a graph, or visualizing a tag cloud. Our contribution is a new overlap removal algorithm that iteratively builds a Minimum Spanning Tree on a Delaunay triangulation of the node centers and removes the node overlaps by "growing" the tree. The algorithm is simple to implement, yet it produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.
Submitted: December 2016.
Reviewed: December 2016.
Revised: January 2017.
Reviewed: March 2017.
Revised: May 2017.
Reviewed: June 2017.
Revised: June 2017.
Accepted: July 2017.
Final: July 2017.
Published: October 2017.
Communicated by Yifan Hu and Martin Nöllenburg
article (PDF)