ImPrEd: An Improved Force-Directed Algorithm

An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges Paolo Simonetto1, Daniel Archambault2, David Auber1, and Romain Bourqui1 1LaBRI, Université Bordeaux 1 — INRIA, Bordeaux Sud-Ouest 2University College Dublin Abstract PrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has

a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly- restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundar- ies. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd. Categories and Subject Descriptors (according to ACM CCS): G.2.2 [Discrete Mathematics]: Graph Theory—Graph Algorithms 1. Introduction PrEd [Ber00] is a force-directed algorithm [Ead84, FR91] that preserves the edge crossing properties of an input layout. The algorithm computes the maximal displacement of nodes and restricts their movement to guarantee this property. The author of PrEd suggested two possible applications: improving the layout [Pur97] of planar, straight-line graph drawing algorithms [DFPP90] and driving force-directed graph layout interactively. By realising that not only does PrEd preserve all edge crossings in an existing layout but actually prevents nodes from crossing edges, we can apply this algorithm to a wider range of problems beyond those stated in the original paper. For example, PrEd can be used to improve Euler-like diagrams [SAA09] where nodes are set elements and edges are set boundaries. In general, we can use PrEd for tasks where we would like to bound portions of a layout, extending the applicability beyond “preserving edge crossing properties” [Ber00]. The contribution of this paper is ImPrEd: an improved force-directed algorithm that prevents nodes from crossing edges. ImPrEd is faster than PrEd and grants greater out- put control. Our test cases provide some evidence that it has improved visual quality. The modifications made, initially motivated by the problem of drawing Euler-like diagrams, can also be useful for general graph drawing. 2. Previous and Related Work Many approaches aim to constrain or restrict node move- ment in force-directed algorithms. Mental map preservation techniques, described in Section 2.1, restrict node...

Website: hal.inria.fr | Filesize: -
No of Page(s): 10
Download ImPrEd: An Improved Force-Directed Algorithm that ... - HAL-Inria.pdf