Tracé de graphesEn 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ésLes 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éthodesFondées sur ces concepts et problématiques, différentes stratégies de dessin de graphes existent, telles que:
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étriquesIl 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 aussiArticles connexesBibliographie
Liens externesExemples de layouts de graphes:
Une collection de layouts de graphes animés interactivement:
Outils de tracés de layout de graphes
Formats de graphes |