graphe planaire

COMBINATOIRE

En théorie des graphes, un graphe planaire est un graphe que l’on peut représenter dans un plan sans que les arêtes (ou arcs si le graphe est orienté) se croisent.
Leur étude permet de résoudre des problèmes tels que celui des trois maisons (posé par Dudeney sous la forme : Un lotissement de trois maisons doit être équipé d’eau de gaz et d’électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire ?) ou celui des quatre couleurs (il est toujours possible, en n’utilisant que quatre couleurs différentes, de colorer une carte découpée en régions connexes, de sorte que deux régions adjacentes – c’est-à-dire ayant toute une frontière en commun, et pas simplement un point – reçoivent toujours deux couleurs distinctes).
En 1930 le mathématicien polonais Kazimierz Kuratowski a caractérisé les graphes planaires : « Un graphe fini est planaire si et seulement s’il ne contient pas de sous-graphe qui est une expansion de K5 ou K3,3 (le graphe complet biparti à 3+3 sommets). », avec les définitions suivantes :
Une expansion d’un graphe est résultat de l’ajout d’un ou plusieurs sommets sur une ou plusieurs arêtes.
Le graphe K5 est le graphe complet à 5 sommets, c’est-à-dire le graphe qui relie par une arête tout couple de sommets pris parmi 5.
K3,3 a 6 sommets et 3×3 = 9 arêtes, chacun des trois premiers sommets étant relié à chacun des trois autres.