Dynamic graph drawing with a hybridized genetic algorithm

Abstract : Automatic graph drawing algorithms, especially those for hierarchical digraphs, have an important place in computer-aided design software or more generally in software programs where an efficient visualization tool for complex structure is required. In these cases, aesthetics plays a major role for generating readable and understandable layouts. Besides, in an interactive approach, the program must preserve the mental map of the user between time t-1 and t. In this paper we introduce a dynamic drawing procedure for hierarchical digraph drawing. It tends to minimize arc-crossing thanks to a hybridized genetic algorithm. The hybridization consists of a local optimization step based on averaging heuristics and two problem-based crossover operators. A stability constraint based on a similarity measure is used to preserve the likeness between the layouts at time t-1 and t. Computational experiments have been done with an adapted random graph generator to simulate the construction process of 90 graphs. They confirm that, because of the actual algorithm, the arc crossing number of the selected layout is close to the best layout found. We show that computation of the similarity measure tends to preserve the likeness between the two layouts.
Type de document :
Communication dans un congrès
I.C. Parmee. Adaptive Computing in Design and Manufacture VI, 2004, Bristol, United Kingdom. Springer, pp.365-375, 2004, Adaptive Computing in Design and Manufacture VI. 〈10.1007/978-0-85729-338-1_31〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00335944
Contributeur : Bruno Pinaud <>
Soumis le : vendredi 31 octobre 2008 - 11:46:30
Dernière modification le : jeudi 5 avril 2018 - 10:36:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 22:32:05

Fichier

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

Identifiants

Collections

Citation

Bruno Pinaud, Pascale Kuntz, Rémi Lehn. Dynamic graph drawing with a hybridized genetic algorithm. I.C. Parmee. Adaptive Computing in Design and Manufacture VI, 2004, Bristol, United Kingdom. Springer, pp.365-375, 2004, Adaptive Computing in Design and Manufacture VI. 〈10.1007/978-0-85729-338-1_31〉. 〈inria-00335944〉

Partager

Métriques

Consultations de la notice

157

Téléchargements de fichiers

111