Force-transfer: a new approach to removing overlapping nodes in graph layout

Swinburne Research Bank (Swinburne University of Technology)Published 1 February 2003Open access

Xiaodi Huang, Wei Lai

Citations25

TL;DR

The Force-Transfer algorithm is proposed to give a new efficient approach to removing overlapping nodes by employing a heuristic method to approximate the global optimal adjustment with the local minimal movement.

Abstract

Graphs where each node includes an amount of text are often used in applications. A typical example of such graphs is UML diagrams used in CASE tools. To make text information in each node readable in displaying such graphs, it is required there should be no overlapping nodes. This paper proposes the Force-Transfer algorithm to give a new efficient approach to removing overlapping nodes. The proposed approach employs a heuristic method to approximate the global optimal adjustment with the local minimal movement. Scanning from the seed node, the approach orthogonally transfers the minimum forces to only those nodes recursively overlapping with the node from where the forces start. We compare the Force-Transfer with the Force-Scan algorithm by mathematical proofs and experiments. The Force-Transfer approach can generate better results.

Keywords

Computer Science

Tabu Search

5,702 Citations1997Fred Glover, Manuel Laguna

Graph Drawing: Algorithms for the Visualization of Graphs

1,996 Citations1998Giuseppe Di Battista, Peter Eades +2 more

Journal of Visual Languages & ComputingLayout Adjustment and the Mental Map

542 Citations1995Kazuo Misue, Peter Eades +2 more

This paper discusses some layout adjustment methods and the preservation of the 'mental map' of the diagram, and two kinds of layout adjustments are described, an algorithm for rearranging a diagram to avoid overlapping nodes and a method aimed at changing the focus of interest of the user without destroying the mental map.

ACM Transactions on GraphicsDrawing graphs nicely using simulated annealing

489 Citations1996Ron Davidson, David Harel

The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely,” and the algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result.

View PDF

Journal of Graph Algorithms and ApplicationsAlgorithms for Cluster Busting in Anchored Graph Drawing

67 Citations1998Kelly Lyons, Henk Meijer +1 more

View PDF

Lecture notes in computer scienceGraph layout adjustment strategies

62 Citations1996M.-A. Storey, Hausi Müller

The SHriMP (SimpleHierarchicalMultiPerspective) visualization technique uses this layout adjustment algorithm to create fisheye views of nested graphs which preserves straightness of lines and uniformly resizes nodes when requests for more screen space are made.

View PDF

ConstraintsRemoving Node Overlapping in Graph Layout Using Constrained Optimization

47 Citations2003Kim Marriott, Peter J. Stuckey +2 more

This work proposes four different approaches for removing node overlapping, all of which are based on constrained optimization techniques, and one of which is an adaptation of the EGENET solver originally designed for solving general constraint satisfaction problems.

ConstraintsConstrained Graph Layout

41 Citations1998Weiqing He, Kim Marriott

This work describes four implementations of layout modules which are based on the constrained graph layout model and shows that they are quite fast and give reasonable layout.

Information Processing LettersRemoving edge-node intersections in drawings of graphs

26 Citations2002Wei Lai, Peter Eades

This paper describes a kind of graph where nodes vary in shape and size a practical graph, and shows how classical algorithms can be applied to draw graphs arising in practice as long as nodes take very little space.

Systems and Computers in JapanA layout adjustment problem for disjoint rectangles preserving orthogonal order

10 Citations2002Kunihiko Hayashi, Michiko Inoue +2 more

It is shown that the corresponding decision problem for this problem is NP-complete and an O(n2)-time heuristic algorithm for the problem that finds a layout with smaller area than Misue's is presented.