Skip to Main content Skip to Navigation
Conference papers

Dessin de graphe assisté par un algorithme génétique

Maurin Nadal 1, 2, * Guy Melançon 1, 2 
* Corresponding author
1 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 : Interactive visualization interfaces for graph are an interesting perspective for data analysis, and by extension for decision support system. The aim of this project is to assist user for drawing graphs. Currently, one of the main difficulties for the user is to choose the best fitted algorithm for his graph. Indeed, there are lots of different algorithms and few of them are easy to use. The suggested solution is to generate different correct drawings for the same graph. Those drawings are generated by a modified force-directed placement algorithm for which parameters are set vertex by vertex. Parameters set are given by a genetic algorithm. English version : Interactive visualization interfaces for graph are an interesting perspective for data analysis, and by extension for decision support system. The aim of this project is to assist user in drawing graphs. Currently, one of the main difficulties for the user is to choose the best fitted algorithm for his graph. Indeed, there are lots of different algorithms and few of them are easy to use. The suggested solution is to generate different correct drawings for the same graph. Those drawings are generated by a modified force-directed placement algorithm for which parameters are set vertex by vertex. Parameter sets are given by a genetic algorithm. This article presents a proof of concept that this modified algorithm and the associated genetic algorithm are able to reproduce highly constrained drawing (parallel edges or right-angled) in a very different way that what force directed placement algorithms do. The different highlighted points in this article are the mass-spring system and its modification, the genetic algorithm, the similarity method used to evaluate drawing and the proof of concept of the method.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00780201
Contributor : Guy Melançon Connect in order to contact the contributor
Submitted on : Wednesday, January 23, 2013 - 2:51:15 PM
Last modification on : Saturday, June 25, 2022 - 8:29:44 PM
Long-term archiving on: : Wednesday, April 24, 2013 - 3:55:44 AM

File

majecstic2012_submission_11.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00780201, version 1

Collections

Citation

Maurin Nadal, Guy Melançon. Dessin de graphe assisté par un algorithme génétique. 9ème édition de la conférence MAnifestation des JEunes Chercheurs en Sciences et Technologies de l'Information et de la Communication - MajecSTIC 2012 (2012), Nicolas Gouvy, Oct 2012, Villeneuve d'Ascq, France. ⟨hal-00780201⟩

Share

Metrics

Record views

342

Files downloads

619