Premium
ImPrEd: An Improved Force‐Directed Algorithm that Prevents Nodes from Crossing Edges
Author(s) -
Simonetto Paolo,
Archambault Daniel,
Auber David,
Bourqui Romain
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.01956.x
Subject(s) - computer science , algorithm , graph , graph layout , graph drawing , planar , planar graph , enhanced data rates for gsm evolution , set (abstract data type) , theoretical computer science , topology (electrical circuits) , mathematics , artificial intelligence , computer graphics (images) , combinatorics , programming language
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 boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEdproves to be consistently faster than PrEd.