- Trace de graphes
-
Tracé de graphes
En théorie des graphes, le tracé de graphes s'applique à une topologie et géométrie pour produire une représentation à deux ou trois dimensions des graphes. 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.
Sommaire
Méthodes
Les graphes sont généralement représentés en images en utilisant des points pour représenter les sommets, et des arcs pour représenter les arêtes entre les sommets reliés. Des flèches peuvent être utilisées pour montrer l'orientation des graphes orientés. 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 arrêtes impacte la compréhensibilité, l'usabilité, le coût de fabrication et l'esthétique.
Basé sur ces concepts et problèmatiques, différentes stratégies de dessin de graphes existent, telles que:
- force-based layout: gradient-descent minimization of an energy function based on physical metaphors.
- spectral layout: layout basé sur une fonction energie qui est amenable à de la minimisation globale basé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 symmetries dans le graphe.
- dessins arborescents : montrent un arbre-like formation, utile pour les arbres (i.e. les graphes sans cycles)
- dessins hierarchiques : 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
Il n'y a pas de "meilleur" layout — différentes manière 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'entrecoupants. Alors que certains graphes ne peuvent être traçé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 croisement que possible.
Voir aussi
- Diagramme états-transitions
- Molecular mechanics
Références
- Giuseppe Di Battista, Peter Eades, 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). http://www.cs.brown.edu/people/rt/gd.html
- Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf
Liens externes
Exemples de layouts de graphes:
- http://pigale.sourceforge.net/images.html
- http://www.dia.uniroma3.it/~gdt/editablePages/sample_applications.htm
- http://www.tomsawyer.com/gallery/gallery.php
- http://www.aisee.com/gallery
- http://www.research.att.com/sw/tools/graphviz/examples/
- http://www.yworks.com/en/products_yfiles_practicalinfo_gallery.htm
- VisualComplexity.com - A visual exploration on mapping complex networks
Une collection de layouts de graphes animés interactivement:
- http://www.ilog.com/products/jviews/demos/index.cfm
- http://www.yworks.com/en/products_yfiles_practicalinfo_demos.htm
- http://www.tensegrity-software.com/graph-demo.html
- 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).
- OpenProblem - a wiki for keeping track of the open problems in the field of graph drawing
Outils de tracés de layout de graphes
- http://aragorn.ads.tuwien.ac.at/AGD/
- http://pigale.sourceforge.net
- http://www.dia.uniroma3.it/~gdt/
- http://www.tomsawyer.com
- Graphviz : http://www.graphviz.org
- http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html
- http://www.aisee.com
- http://www.tulip-software.org
- http://www.oreas.com/
- http://www.ilog.com/products/jviews/graphlayout/
- http://www.algorithmic-solutions.com/enalgocomsdiagram.htm
- http://www.jgraph.com/
- http://www.yworks.com/en/products.htm
- ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz
- http://gravisto.fim.uni-passau.de
- http://www.wilmascope.org
- http://www.cs.uleth.ca/~vpak/gluskap
- http://jung.sourceforge.net
- http://www.tensegrity-software.com
Formats de graphes
Catégorie : Théorie topologique des graphes
Wikimedia Foundation. 2010.