Dans la théorie des graphes, un graphe planaire est un graphe quelconque 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.
1) 2) 3) 4)
En fait, K5 et K3,3 sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.
Le mathématicien polonais Kazimierz Kuratowski a établi la caractérisation suivante des graphes planaires :
L'expansion 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 •—•—•).
Voici un problème classique du cavalier aux échecs. 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.
La propriété du graphe planaire ne sert souvent que l'intérêt de savoir s'il est possible de présenter facilement les problèmes au cerveau humain ; pour la machine, si les algorithmes n’utilisent pas de recherche topographique et que le graphe n'est pas réorganisé, cela revient au même.