Node overlap removal for 1D graph layout

Fadloun Samilha, Poncelet Pascal, Rabatel Julien, Roche Mathieu, Sallaberry Arnaud. 2017. Node overlap removal for 1D graph layout. In : 21st International Conference Information Visualisation (IV). Information Visualisation Society. Londres : IEEE, pp. 224-229. International Conference Information Visualisation (IV). 21, Londres, Royaume-Uni, 11 July 2017/14 July 2017.

Paper with proceedings
[img] Published version - Anglais
Access restricted to CIRAD agents
Use under authorization by the author or CIRAD.

Télécharger (1MB) | Request a copy

Url - éditeur :

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. (Résumé d'auteur)

Mots-clés libres : Data visualization

Classification Agris : U10 - Computer science, mathematics and statistics
C30 - Documentation and information
000 - Other themes

Auteurs et affiliations

  • Fadloun Samilha, LIRMM (FRA)
  • Poncelet Pascal, LIRMM (FRA)
  • Rabatel Julien, LIRMM (FRA)
  • Roche Mathieu, CIRAD-ES-UMR TETIS (FRA) ORCID: 0000-0003-3272-8568
  • Sallaberry Arnaud, LIRMM (FRA)

Source : Cirad-Agritrop (

View Item (staff only) View Item (staff only)

[ Page générée et mise en cache le 2021-02-02 ]