Node Overlap Removal for 1D Graph Layout

Abstract : Energy based algorithms are powerful techniques for laying out graphs. They tend to generate aesthetically pleasing graph embeddings, exhibiting symmetries and community structures. When dealing with large graphs, an important drawback of these algorithms is to produce embeddings where many nodes overlap, leading to cluttering issues. While several approaches have been proposed for node overlap removal on 2D graph layouts, to the best of our knowledge, there is no work dedicated to 1D graph layouts. In this paper, we first define 4 requirements for 1D graph node overlap removal. Then, we propose a O(|V|log(|V|)) time algorithm meeting these requirements. We illustrate our approach with two case studies based on arc diagrams where nodes are positioned by applying a MDS technique to highlight community structures. Finally, we compare our technique with alternatives from 2D graph techniques, and a discussion highlights some properties of the results.
Type de document :
Communication dans un congrès
iV: Information Visualisation, Jul 2017, London, United Kingdom. 21st International Conference Information Visualisation, 2017, 〈http://www.graphicslink.co.uk/IV2017/〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01542283
Contributeur : Pascal Poncelet <>
Soumis le : jeudi 13 juillet 2017 - 09:01:59
Dernière modification le : samedi 25 novembre 2017 - 10:16:15

Fichier

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

Identifiants

  • HAL Id : lirmm-01542283, version 2

Citation

Samiha Fadloun, Pascal Poncelet, Julien Rabatel, Mathieu Roche, Arnaud Sallaberry. Node Overlap Removal for 1D Graph Layout. iV: Information Visualisation, Jul 2017, London, United Kingdom. 21st International Conference Information Visualisation, 2017, 〈http://www.graphicslink.co.uk/IV2017/〉. 〈lirmm-01542283v2〉

Partager

Métriques

Consultations de la notice

265

Téléchargements de fichiers

84