Graphe planaire

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, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. 1) 2) 3) 4) Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes. 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. C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire. C'est un graphe biparti complet K3,3 à 6 sommets, 3 d'entre eux se connectant aux trois autres. 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. vignette|Le graphe des pays du monde reliés par un arête s'ils sont limitrophes n'est pas planaire car il possède une expansion de K5 parmi ses sous-groupes partiels. Le mathématicien polonais Kazimierz Kuratowski a établi en 1930 la caractérisation suivante des graphes planaires : Un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphe partiel qui est une expansion de K5 (le graphe complet à 5 sommets) ou K3,3 (le graphe complet biparti à 3+3 sommets). L'expansion (ou subdivision) 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 •—•—•). Quelques années plus tard le mathématicien allemand Klaus Wagner en donna une caractérisation semblable : Un graphe fini est planaire si et seulement s'il ne compte pas K5 ou K3,3 parmi ses mineurs.