User Tools

Site Tools


chicoutimi_2016:dessin_de_graphes

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Dessin de graphes

Dessin de graphes: Graph Drawing, c'est le nom sous lequel cette “discipline” est connue.

Dessiner un graphe, c'est rendre sa structure “facilement” lisible. Facile à dire.

Un dessin d'un graphe est une application (ou ).

Un graphe est un espace topologique, c'est-à-dire que ses éléments sont équipés d'une métrique – une fonction de distance

  • et (réflexivité)
  • (symétrie)
  • (inégalité triangulaire)

Et, pour des raisons qui s'éclairciront, un dessin lisible est un dessin qui rend compte au mieux des distances entre les éléments du graphe. En d'autres mots, la distance euclidienne dans le plan entre les positions données à et est “proche” de la distance entre et dans le graphe (pour tous les sommets ).

Exercise Give an example of a graph where the distance constraint underlined above is unsatisfiable.

Parce que cette contrainte (sur la distance euclidienne versus ) ne peut être satisfaite, on convient d'objectifs “esthétiques” que tout algorithme doit chercher à satisfaire “au mieux”.

  • Longueur uniforme des arêtes dans le graphe (pour réfléter au mieux la distance d'nu chemin comme la somme des longueurs des arêtes qui le constituent).
  • Eviter les croisements des arêtes – en lien avec la contrainte, le croisement reste souvent inévitable pour réaliser un dessin dans . Un graphe qui admet un dessin sanscroisement d'arêtes est dit planaire.
  • D'autres critères sont plus spécifiques et reposent sur la structure particulière des graphes.
    • Les arbres réflètent le plus souvent une structure hiérarchique (un organigramme, une généalogie, etc.).
    • Les graphes orientés sans cycle (appelé aussi dag ou DAG pour “directed acyclic graphs”) possède un ordre naturel. Les sommets sont ordonnées depuis les sommets sources (qui n'ont pas de prédécesseurs), jusqu'aux sommets puits (qui n'ont pas de successeurs).
    • Les graphes planaires qui admettent un dessin sans croisement d'arêtes.

Pour tout savoir sur le dessin de graphes:

  • Les monographies co-écrites par des chercheurs fondateurs du domaines:
    • di Battista, G., P. Eades, et al. (1998). Graph Drawing: Algorithms for the Visualisation of Graphs, Prentice Hall.
    • Kaufmann, M. and D. Wagner, Eds. (2001). Drawing Graphs, Methods and Models. Lecture Notes in Computer Science 2025, Springer.
  • Les articles des actes du Symposium Graph Drawing, toujours publiés dans la série Lecture Notes in Computer Science de Springer.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/dessin_de_graphes.txt · Last modified: 2016/05/05 17:16 by melancon