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 produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.
Another set of node overlap removal algorithms focus on the idea of defining pairwise node constraints and translating the nodes to satisfy the constraints . These methods consider horizontal and vertical problems separately, which often leads to a distorted aspect ratio . A Force-transfer-algorithm is introduced by @cite_3 ; horizontal and vertical scans of overlapped nodes create forces moving nodes vertically and horizontally; the algorithm takes @math steps, where @math is the number of the nodes. @cite_1 develop Mixed Integer Optimization for Layout Arrangement to remove overlaps in a set of rectangles. The paper discusses the quality of the layout, which seems to be high, but not the effectiveness of the method, which relies on a mixed integer problem solver. @cite_5 reduce the overlap removal to a quadratic problem and solve it efficiently in @math steps. According to Gansner and Hu @cite_0 , the quality and the speed of the method of @cite_5 is very similar to the ones of PRISM.
@cite_0 @cite_5 @cite_1 @cite_3
2098329200 1584926591 2069391844 2031908202
When drawing graphs whose nodes contain text or graphics, the nontrivial node sizes must be taken into account, either as partof 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. Thispaper 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 ofthe analysis, we consider and evaluate two measures of dissimilarity for two layouts of the same graph. 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 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. Arranging geometric entities in a two-dimensional layout is a common task for most information visualization applications, where existing algorithms typically rely on heuristics to position shapes such as boxes or discs in a visual space. Geometric entities are used as a visual resource to convey information contained in data such as textual documents or videos and the challenge is to place objects with similar content close to each other while still avoiding overlap. In this work we present a novel mechanism to arrange rectangular boxes in a two-dimensional layout which copes with the two properties above, that is, it keeps similar object close and prevents overlap. In contrast to heuristic techniques, our approach relies on mixed integer quadratic programming, resulting in well structured arrangements which can be easily be tuned to take different forms. We show the effectiveness of our methodology through a comprehensive set of comparisons against state-of-art methods. Moreover, we employ the proposed technique in video data visualization, attesting its usefulness in a practical application. Techniques for drawing graphs have proven successful in producing good layouts of undirected graphs. When nodes must be labeled however, the problem of overlapping nodes arises, particularly in dynamic graph visualization. Providing a formal description of this problem, this paper presents a new approach called the Force-Transfer algorithm that removes node overlaps. Compared to other methods, our algorithm is usually able to achieve a compact adjusted layout within a reasonable running time.