Dessiner un graphe planaire.
Les graphes planaires sont ceux qui peuvent être dessinés dans le plan sans que leurs arêtes se croisent. En cours, nous verrons des caractérisations de ces graphes, notamment par mineurs exclus (théorème de Kuratowski), et nous discuterons des problèmes de coloration pour cette classe. Par contre, nous ne donnerons pas d'algorithme pour tester si un graphe est planaire à partir de ses listes d'adjacences (ou de sa matrice d'adjacence) et si oui, pour dessiner ce graphe dans le plan sans croisement d'arêtes. Pour désigner une telle représentation, on parle parfois de plongement du graphe dans le plan ou de carte planaire du graphe. Les algorithmes de dessin de graphes planaires ont de nombreuses applications comme en cartographie, en conception de circuits intégrés VLSI, pour les interfaces de visualisation de données ...
L'objectif du sujet est de présenter des algorithmes qui reconnaissent les graphes planaires et sont capables d'en faire des dessins intéressants. Parmi les points abordables :
- Présenter un algorithme efficace de reconnaissance des graphes planaires (on peut arriver en complexité linéaire) et présenter un algorithme efficace de dessin sans croisement d'arêtes (reconnaissance et dessin peuvent être éventuellement réalisés par un même algorithme).
- Des conditions supplémentaires sont parfois imposées aux dessins que l'on souhaite obtenir, par exemple sommets représentés par des rectangles et arêtes sous forme de lignes brisées qui sont des suites de segments horizontaux ou verticaux (box-orthogonal drawings). Ces dessins particuliers s'appliquent parfois à tous les graphes planaires, mais parfois seulement à une partie d'entre eux, et des algorithmes spécifiques existent pour réaliser ces dessins. Vous pouvez présenter certains de ces résultats en guise d'illustration.
Quelques références (pas
exhaustif).
- Introduction to Graph Theory, livre de D. West, Prentice Hall (2001). Un chapître sur les graphes planaires, qui contient en autre un algorithme de reconnaissance.
- Planar Graph Drawing, livre de T. Nishizeki et S.Rahman, Lecture Notes Series on Computing, World Scientific (2004). Un livre de référence sur le dessin de graphes planaires.
Retour à la page des sujets.