Tracé de graphes
En théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique.
Types de tracés
Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation. Cette représentation graphique ne doit pas être confondue avec le graphe lui-même (la structure abstraite et non graphique). Des dessins très différents peuvent correspondre au même graphe. La seule chose qui compte vraiment est le nombre d'arêtes entre chaque paire de sommets. En pratique, cependant l'arrangement de ces nœuds et arêtes influence la compréhensibilité, l'usabilité, le coût de fabrication et l'esthétique.
D'autres exemples de conventions sont la représentation par intersection et les représentations de la matrice d'adjacence.
Méthodes
Fondées sur ces concepts et problématiques, différentes stratégies de dessin de graphes existent, telles que:
- Layout dirigé par les forces : minimisation par descente de gradient d'une fonction d'énergie, inspiré par une métaphore physique.
- spectral layout: layout basé sur une fonction énergie qui est amenable à de la minimisation globale fondée sur des techniques d'algèbre linéaire.
- orthogonal layout: layout avec des arcs courant horizontalement et verticalement, avec des approches pour réduire le nombre d'arcs s'entrecoupant ainsi que la superficie. Ils sont d'un grand intérêt dans le domaine de VLSI et conception de PCB .
- symmetric layout: ils essayent de trouver les groupes de symétries dans le graphe.
- dessins arborescents : techniques spécialisées pour le tracé d'arbre.
- dessins hiérarchiques : essayent de trouver une source et un puits dans un graphe orienté et d'arranger les nœuds en strates en ayant le plus d'arcs commençant vers la source et suivant la direction du puits.
Dans certaines applications de tracé de graphes, il est important de formellement spécifier la mise en œuvre et la vérification formelle de ces procédures.
Métriques
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/59/Complete_graph_K4.svg/150px-Complete_graph_K4.svg.png)
Il n'y a pas de « meilleur » tracé — différentes manières d'afficher un graphe montrent différentes caractéristiques. Une métrique d'un algorithme de tracé de graphes est le nombre d'arcs s'entrecoupant. Alors que certains graphes ne peuvent être tracés sans que les arcs s'entrecoupent, certains graphes peuvent l'être, on les appelle des graphes planaires. D'après cette métrique, les « bons » algorithmes tracent des graphes avec aussi peu de croisements que possible. Le nombre minimal de croisements d'un graphe possible mesure cette propension.
Voir aussi
Articles connexes
Bibliographie
- Giuseppe Di Battista, Peter Eades (en), Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
- Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). www.cs.brown.edu
- Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. www.cs.brown.edu
Liens externes
Exemples de layouts de graphes:
- PIGALE Images
- www.dia.uniroma3.it
- Data Visualization Software | Tom Sawyer Software Image Gallery
- aiSee Graph Gallery
- Graphviz
- yWorks - Products
- VisualComplexity.com - A visual exploration on mapping complex networks
Une collection de layouts de graphes animés interactivement:
- IBM ILOG Visualization for Java
- yWorks - Products
- Tensegrity Software - Graph Framework Sample Applications
- GD 2005 (Limerick, Ireland) -- One of the top academic conferences for new research in graph drawing is the annually held International Symposium on Graph Drawing (GD).
- graphdrawing.org - Site fournissant des points d'entrée sur les problématiques des graphes.
Outils de tracés de layout de graphes
- aragorn.ads.tuwien.ac.at
- pigale.sourceforge.net - Public Implementation of a Graph Algorithm Library and Editor.
- GDToolkit - Boite à outils pour dessiner des graphes comportant une interface de programmation orienté objet (GAPI) et gestion par lot via une ligne de commande (BLAG).
- www.tomsawyer.com - Ensemble de services pour créer, manipuler et afficher des graphes.
- Graphviz : www.graphviz.org - Visualisation de graphe supportant le langage DOT.
- www.cs.uni-sb.de
- www.aisee.com
- www.tulip-software.org
- www.oreas.com
- IBM ILOG Visualization for Java
- www.algorithmic-solutions.com
- www.jgraph.com
- yWorks - Products - Ensemble de service pour créer/éditer des graphes (yEd).
- ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz
- https://github.com/Gravisto/Gravisto - Visualisation et édition de graphes.
- www.wilmascope.org
- ..:: GLuskap ::..
- jung.sourceforge.net - Outil de modélisation, d'analyse et d'édition de graphes développé en Java.
- www.tensegrity-software.com
Formats de graphes
- GML
- GraphML
- GraphXML
- GXL
- GEXF
- DOT
Portail de l'informatique théorique