Dans la Théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune Arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan.

Exemples et contre-exemples

1) 2) 3) 4)

1. Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.
2. C'est un Graphe complet à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle 1 2 3, on constate qu'il n'y a plus d'intersection d'arêtes.
3. C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.
4. C'est un graphe complet biparti à 6 sommets, 3 d'entre eux se connectant aux trois autres (K3,3). Il n'est pas planaire.

En fait, K5 et K3,3 sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.

Caractérisation de Kuratowski

Le Mathématicien Polonais Kazimierz Kuratowski a établi la caractérisation suivante des graphes planaires :

Un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphe qui est une expansion de K₅ (la clique à 5 sommets) ou K_3,3 (le graphe complet biparti à 3+3 sommets).

Lexpansion d'un graphe est le résultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arêtes (par exemple, transformation de l'arête •——• en •—•—•). En d'autres termes, un graphe est planaire si et seulement s'il ne contient pas de mineur K5 ni K3,3.

Intérêt

L'intérêt pour les graphes planaires remonte au théorème des quatre couleurs. Depuis, de nombreux problèmes intrinsèquement difficiles du point de vue algorithmique (NP-complet) se sont avérés faciles dans cette classe particulière ; toutefois pour la plupart de ces problèmes seule l'interdiction du mineur K5 est nécessaire.

La propriété de planarité est à l'origine des questions plus générales de plongement de graphe sur des surfaces (graph embedding) : peut-on plonger un graphe donné sur une surface donnée ?

La propriété de planarité d'un graphe le rend plus abordable au Cerveau humain comme en témoigne l'exemple du problème du cavalier aux échecs ci-dessous :

Sur un échiquier, on dispose un cavalier. Le but est de le faire passer par toutes les cases, une seule fois par case, en respectant le mouvement classique de la pièce aux échecs. Pour illustrer le problème, on utilise ici un plateau de quatre cases sur trois rangées. Le problème est représenté par un graphe de mouvement ; les sommets du graphe correspondent aux cases de l’échiquier ; les arcs figurent les mouvements possibles. Ainsi, à partir de la case 1, il est possible de se rendre à la case 8 ou à la case 6 car celles-ci sont liées à la première sur le graphe.

Présenté de cette manière, le problème reste complexe. Toutefois, le graphe est planaire et on peut le représenter de façon plus intuitive. On peut facilement extraire de cette nouvelle représentation une solution (tracée en vert) partant de la case 3 et arrivant à la case 10.

De façon plus terre à terre, il était plus facile de concevoir les tout premiers circuits imprimés à transistors quand le graphe du circuit était planaire : on évitait alors de devoir recourir au procédé bicouche ou à des "straps" fragiles pour s'échapper du plan du circuit imprimé.

Liens externes

• bibliothèque d'algorithmes et éditeur de graphes — bibliothèque d'algorithmes sur les graphes en GPL, parmi lesquels un test de planarité, une représentation planaire, une exhibition de sous-graphes de Kuratowski en temps linéaire.
• Planarity — pour jouer avec les graphes planaires.