ImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges

Paolo Simonetto 1, 2 Daniel Archambault 3 David Auber 1, 2 Romain Bourqui 1, 2
2 GRAVITE - Graph Visualization and Interactive Exploration
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : PrEd 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, ImPrEd proves to be consistently faster than PrEd.
Type de document :
Article dans une revue
Computer Graphics Forum, Wiley, 2011, IEEE Symposium on visualization 2011 (EuroVis 2011), 30 (3), 〈https://diglib.eg.org/EG/DL/CGF/volume30/issue3〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00605921
Contributeur : Paolo Simonetto <>
Soumis le : lundi 8 août 2011 - 19:20:05
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : jeudi 30 mars 2017 - 12:41:15

Fichier

EuroVis11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00605921, version 1

Citation

Paolo Simonetto, Daniel Archambault, David Auber, Romain Bourqui. ImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges. Computer Graphics Forum, Wiley, 2011, IEEE Symposium on visualization 2011 (EuroVis 2011), 30 (3), 〈https://diglib.eg.org/EG/DL/CGF/volume30/issue3〉. 〈inria-00605921〉

Partager

Métriques

Consultations de la notice

331

Téléchargements de fichiers

217