Les graphes planaires.

Les graphes planaires sont ceux qui peuvent être dessinés dans le plan sans que leurs arêtes se croisent. On y est confrontré très tôt avec ce petit puzzle classique qui consiste à dessiner trois maisons, puis trois sources d'éenergie (eau, gaz, électricité) et ensuite à demander de relier toutes les maisons à toutes les sources d'énergie sans que deux liaisons ne se croisent. C'est impossible et la démonstration demande un petit peu de travail (par exemple avec l'utilisation de la formule d'Euler). Les graphes planaires sont à l'origine de très nombreux travaux, autour de grandes conjectures comme le théorème des quatre couleurs et d'applications variées comme par exemple la conception de circuits intégrés.

L'objectif du sujet est de donner une inroduction aux graphes planaires. Parmi les points abordables :

• Définition et premières propriétés des graphes planaires.
• Une (ou plusieurs) caractérisation(s), comme celle de Kuratowski par mineurs topologiques interdits.
• Un algorithme de reconnaissance et de dessin des graphes planaires.
  

Quelques références (pas exhaustif).

• Graph Theory, livre de R. Diestel, Springer (2000). Un chapître sur les graphes planaires.
• 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.

Retour à la page des sujets.