Voir la source de Graphe planaire

{{Voir homonymes|Planaire}}
{{ébauche|mathématiques}}

Dans la [[théorie des graphes]], un '''graphe planaire''' est un [[graphe (théorie des graphes)|graphe]] qui a la particularité de pouvoir se représenter sur un [[plan (mathématiques)|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 [[plongement#Espaces topologiques|plonger]] dans le plan, ou encore les graphes dont le [[Nombre de croisements (théorie des graphes)|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]].

== Exemples et contre-exemples ==
1)[[Image:Graphe planaire.png|Graphe planaire]]
2)[[Image:Graphe K4.png|Graphe K4]]
3)[[Image:Graphe K5.png|Graphe K5]]
4)[[Image:Graphe K3,3.png|Graphe K3,3]]
# Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.
# C'est un [[graphe complet]] à quatre sommets (K<small>4</small>). 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 (K<small>5</small>). Il n'est pas planaire.
# C'est un [[graphe biparti complet]] ''K''<sub>3,3</sub> à 6 sommets, 3 d'entre eux se connectant aux trois autres. Il n'est pas planaire.

En fait, ''K''<sub>5</sub> et ''K''<sub>3,3</sub> sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.

== Caractérisation de Kuratowski et de Wagner ==
{{confusion|Théorème de fermeture/complémentaire de Kuratowski}}
[[Fichier:K5 Eurasie.svg|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 ''K''<sub>5</sub> parmi ses sous-groupes partiels.]]
Le [[mathématicien]] [[pologne|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 ''K''<sub>5</sub> (le graphe complet à 5 sommets) ou ''K''<sub>3,3</sub> (le graphe complet biparti à 3+3 sommets).
L'''[[Homéomorphisme de graphes|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 [[allemagne|allemand]] [[Klaus Wagner (mathématicien)|Klaus Wagner]] en donna une caractérisation semblable : 
:Un graphe fini est planaire si et seulement s'il ne compte pas ''K''<sub>5</sub> ou ''K''<sub>3,3</sub> parmi ses [[mineur (théorie des graphes)|mineurs]].
Un ''mineur'' d'un graphe est le résultat de la [[contraction d'arête]]s (fusionnant les extrémités), la suppression d'arêtes (sans fusionner les extrémités), et la suppression de sommets (et des arêtes adjacentes).

La différence entre ces deux caractérisations est minuscule, mais Wagner fit la conjecture<ref>Plus précisément, Wagner montra que cette formulation permettait d'énoncer ce qui est à présent connu sous le nom de [[théorème des mineurs]], mais a toujours affirmé qu'il pensait qu'elle serait sans doute réfutée.</ref> que ce dernier admettrait une généralisation que celle de Kuratowski n'admettait pas. Il supposait qu'il y aurait, pour chaque classe de graphes finis close par mineur, un [[ensemble fini]] de ''mineurs interdits'' qui la caractériserait. Une classe est dite ''close par mineur'' si elle comprend tous les mineurs de chaque graphe qu'elle comprend ; un graphe planaire, par exemple, est toujours planaire après la contraction ou suppression d'arêtes et de sommets, et pour cette classe les deux seuls mineurs interdits sont ''K''<sub>5</sub> et ''K''<sub>3,3</sub>. Mais aussi notamment il existerait un nombre fini de mineurs interdits pour la classe des graphes qui peuvent se plonger sur un [[tore]], ou sur une surface quelconque, et pour la classe de graphes qui peuvent se plonger dans l'espace à trois dimensions sans nœud, entre autres. Cette [[conjecture]] fut enfin prouvée en 2004 par Robertson et Seymour, mais de façon non-constructive : par exemple, on ne connaît toujours pas tous les mineurs interdits pour le plongement de graphe sur un tore. Pour plus d'informations, voir l'article [[théorème de Robertson-Seymour]].

== Propriétés ==
[[Fichier:LineGraphExampleA.svg|thumb|Le degré de la face non bornée de ce graphe planaire est égal à 6.]]
[[Fichier:MGWiki1.GIF|thumb|L'arête bleue est une boucle, les arêtes rouges sont multiples.]]
Dans toute la suite du paragraphe, nous utiliserons les notations suivantes :
* <math>G</math> désigne un graphe planaire,
* <math>n</math> son nombre de nœuds, 
* <math>a</math> son nombre d'arêtes (ou de liens),
* <math>f</math> son nombre de faces. 
Une face est une [[connexité (mathématiques)|composante connexe]] du complémentaire du graphe dans le plan. Le degré d'une face <math>F</math> est la longueur de son cycle frontière, on considère un [[chemin (graphe)|chemin]] le plus court possible d'origine confondue avec son extrémité, le nombre d'arêtes (avec leur multiplicité) est le degré de la face <math>F</math>. Il est noté <math> \text{deg}(F)</math>. On obtient une première formule presque évidente<ref>{{Lien web|auteur=T. Chomette|url=http://www.dma.ens.fr/culturemath/maths/pdf/combi/planaire.pdf|titre=Graphes planaires|site=CultureMath, Département de mathématiques appliquées de l'[[École normale supérieure (Paris)|École normale supérieure]]|id=T. Chomette}}, {{p.|1}}.</ref> :
<center><math>(1)\quad \sum_{F} \text{deg}(F) = 2a.</math></center>
En effet, chaque arête élément d'un cycle borde deux faces, une arête partagée par aucun cycle est parcourue deux fois par le chemin frontière de la composante non bornée du complémentaire du graphe.

=== Formule d'Euler et conséquences ===
La [[caractéristique d'Euler|formule d'Euler]] pour un graphe planaire connexe est<ref>{{Harvsp|T. Chomette|p=4}}.</ref> :
<center><math>n-a+f=2.</math></center>
Une méthode simple pour la démontrer est de l'établir pour un graphe sans cycle (à une face), puis par récurrence d'ajouter les arêtes qui engendrent des cycles. Cette formule permet de démontrer que tout graphe simple planaire connexe, ayant au moins trois sommets, vérifie la majoration suivante<ref name="Imrich">{{Ouvrage|langue=en|prénom1=Wilfried|nom1=Imrich|nom2={{Lien|lang=sl|Sandi Klavžar}}|titre=Product Graphs|sous-titre=Structure and recognition|éditeur=[[John Wiley & Sons]]|collection=Wiley-Interscience Series in Discrete Mathematics and Optimization|année=2000|pages totales=|isbn=}}.</ref>.
<center><math>(2)\quad a \le 3n - 6.</math></center>
Un [[graphe (mathématiques discrètes)|graphe simple]] est un graphe sans boucle (une boucle est une arête qui possède une origine et une extrémité confondues) et sans arête multiple (des arêtes multiples sont des arêtes ayant même origine et même extrémité). Cette formule se démontre simplement : toute face est de degré au moins égal à 3, car le graphe comporte au moins trois nœuds et est simple. On en déduit, par la formule (1), que 3''f'' est inférieur ou égal à 2''a''. La formule d'Euler permet de conclure.

Cette formule implique que les graphes planaires sont des [[graphe dense|graphes creux]]. De plus, leur [[arboricité]] est bornée par 3.

Cette majoration est à l'origine d'une démonstration du fait que ''K''<sub>5</sub> n'est pas planaire. En effet, ''K''<sub>5</sub> dispose de 10 arêtes, et 5 nœuds, ce résultat est incompatible avec la majoration (2). Si, avec les hypothèses de la majoration (2), le graphe est [[graphe sans triangle|sans triangle]], on dispose alors de la majoration :
<center><math>(3)\quad a \le 2n - 4.</math></center>

Le raisonnement est le même, mais cette fois-ci le degré d'une face est au moins égal à 4. On en déduit que ''K''<sub>3,3</sub> n'est pas planaire<ref name="Imrich"/>. Les détails sont donnés dans l'article « [[Énigme des trois maisons]] ».

{{démonstration|titre=Démonstration de la formule d'Euler|contenu=
Un premier lemme est utile :
* '''Tout graphe planaire connexe peut s'obtenir en adjoignant des arêtes à un arbre connexe ayant les mêmes nœuds<ref>La proposition ainsi qu'une démonstration est disponible dans {{Harvsp|T. Chomette|p=3}}.</ref> :'''

Un arbre est un graphe ne contenant qu'une unique face. On procède par récurrence  sur ''f'', le nombre de faces du graphe.

Supposons que le graphe ne possède qu'une unique face, le graphe est un arbre et la proposition est trivialement vérifiée. Supposons que la proposition est vraie pour ''f''  et montrons-la pour un graphe ''G'' à ''f''&nbsp;+&nbsp;1 faces. Le [[théorème de Jordan]] montre que s'il existe plusieurs faces, il existe une [[théorème de Jordan|courbe de Jordan]] formée par des arêtes. Si l'on retranche une des arêtes ''A'' de la courbe au graphe ''G'', les parties droite et gauche du complémentaire du graphe, qui formaient précédemment deux faces, n'en font plus qu'une et ce qui reste de la courbe de Jordan garantit que ''G'' est toujours connexe. Le graphe amputé de ''A'' vérifie les hypothèses de récurrence et s'obtient en adjoignant des arêtes à un arbre connexe. Ajouter la dernière arête ''A'' fournit le graphe initial.

* '''Formule d'Euler<ref>Cette démonstration provient de {{Harvsp|T. Chomette|p=4}}.</ref> :'''

Démontrons la proposition tout d'abord pour un arbre, par récurrence sur le nombre ''n'' de ses nœuds. Si l'arbre ne contient qu'un unique nœud, il possède une face et aucune arête, la formule est vérifiée. On suppose que la formule est vraie pour ''n'', montrons-la pour un arbre ''G'' contenant ''n''&nbsp;+&nbsp;1 nœuds. Comme l'arbre ne contient qu'une unique face, il contient au moins un nœud ''N'' connecté à une unique arête (sinon le théorème de Jordan garantirait l'existence d'au moins deux faces.). L'arbre ''G'' privé de ce nœud et de l'arête adjacente est un arbre connexe contenant ''n'' nœuds, il vérifie l'hypothèse de récurrence. Ajouter le nœud ''N'' et l'arête associée correspond à ajouter un nœud et une arête, la formule d'Euler reste vraie pour ''G'', ce qui termine cette première étape.

Démontrons maintenant la proposition pour un graphe connexe, par récurrence sur le nombre ''f'' de ses faces. Si ''f'' est égal à 1, la formule est vérifiée d'après la récurrence précédente. Supposons-la vraie pour tout graphe ayant ''f'' faces et montrons-la pour un graphe ''G'' ayant ''f''&nbsp;+&nbsp;1 faces. La récurrence du lemme montre qu'il est possible de retrancher une arête à ''G'' de manière que le nouveau graphe soit encore connexe et ait exactement ''f'' faces. La formule d'Euler est alors vérifiée par hypothèse de récurrence. Rajouter l'arête manquante ne modifie pas le nombre de nœuds, et incrémente de un le nombre d'arêtes et de faces. La formule d'Euler est encore vérifiée, ce qui termine la démonstration.
}}

== Dessin de graphe ==

La [[conjecture de Scheinerman]], maintenant démontrée, énonce que tout graphe planaire est le [[graphe d'intersection]] de segments dans le plan.

== Intérêt et applications ==
[[Image:Graphe de mouvement du cavalier 3x4.png|frame|right|Un graphe de mouvement brut à gauche ; le même graphe réorganisé à droite.]]

Un exemple simple pour illustrer l'intérêt des graphes planaires est une énigme, dite [[énigme des trois maisons|des trois maisons]] initialement posée sous forme mathématique par H. E. Dudeney en [[1917 en science|1917]]<ref>{{Ouvrage|langue=en|prénom1=Martin|nom1=Gardner|lien auteur1=Martin Gardner|titre=The Sixth Book of Mathematical Games from Scientific American|éditeur=[[University of Chicago Press]]|année=1984|pages totales=|passage=92-94|isbn=0-226-28250-3}}</ref>. Elle prend la forme suivante : « 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<ref>On la trouve sous le nom de {{Citation|Problème des trois villas et des trois usines}} dans {{Ouvrage|prénom1=Claude|nom1=Berge|lien auteur1=Claude Berge|titre=Graphes|éditeur=Gauthier-Villars|année=1983|numéro d'édition=3|pages totales=|passage=17|isbn=978-2-04-015555-1}}</ref> ? »

Cependant, l'intérêt pour les graphes planaires est plus ancien, il remonte au [[théorème des quatre couleurs]]. Depuis, de nombreux problèmes 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 (théorie des graphes)|mineur]] K<small>5</small> 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{{refnec}} comme en témoigne l'exemple du problème du [[Cavalier (jeu d'échecs)|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 [[circuit imprimé|circuits imprimés]] à transistors quand le graphe du circuit était planaire : on évitait alors de devoir recourir au procédé bicouche ou à des « ''{{Lang|en|straps}}'' » fragiles pour s'échapper du plan du circuit imprimé.

== Aspects algorithmiques ==
=== Reconnaissance ===
Le problème qui consiste, étant donné un graphe à savoir si c'est un graphe planaire est appelé [[test de planarité]]. Plusieurs algorithmes ont été proposés pour ce problème. Les meilleurs atteignent une [[complexité en temps|complexité en temps linéaire]], ce qui est optimal asymptotiquement. Le premier tel algorithme date de 1974, et est dû à [[Robert Tarjan]] et [[John Hopcroft]]<ref>
{{article
 | nom1 = Hopcroft | prénom1 = John |lien auteur1=John Hopcroft
 | nom2 = Tarjan | prénom2 = Robert E. | lien auteur2 = Robert Tarjan
 | titre = Efficient planarity testing
 | périodique = [[Journal of the ACM]]
 | doi = 10.1145/321850.321852
 | numéro = 4  | volume = 21 | passage = 549–568
 | année = 1974}}.</ref>.
Robert Cori a décrit l'historique et les principes de cet algorithme dans un article paru dans le ''Bulletin de la société informatique de France''<ref>{{Article
|langue=
|auteur1= Robert Cori
|titre= L'algorithme de test de planarité de R. E. Tarjan
|périodique= 1024– Bulletin de la société informatique de France
|volume=
|numéro= 4
|date= octobre 2014
|pages= 55-65
|issn= 2270-1419
|lire en ligne= https://www.societe-informatique-de-france.fr/wp-content/uploads/2014/10/1024-4-cori.pdf
|consulté le=29 juin 2020
}}.</ref>.
=== Problèmes restreints à la classe ===

Certains [[Problème algorithmique|problèmes algorithmiques]] sont plus faciles à résoudre si on se restreint aux graphes planaires, par exemple le [[problème de l'isomorphisme de graphes]] peut être résolu en temps linéaire<ref>{{chapitre  | prénom1 = John E.  | nom1 = Hopcroft  | lien auteur1 = John Hopcroft  | prénom2 = Jin-Kue  | nom2 = Wong  | titre chapitre = Linear time algorithm for isomorphism of planar graphs  | titre ouvrage = Proceedings of the Sixth Annual ACM [[Symposium on Theory of Computing]]  | année = 1974  | passage = 172–184  | doi = 10.1145/800119.803896}}.</ref>, ce qui a priori n'est pas du tout le cas pour l'ensemble des graphes. De même pour l'[[algorithme d'approximation|approximation]], par exemple le problème [[k-centre]] ne peut pas être approché avec un meilleur ratio que 2 dans le cas général, sauf si [[P=NP]]<ref>
{{article
 | titre= Easy and hard bottleneck location problems
 | auteur1= Wen-Lian Hsu |auteur2= George L. Nemhauser
 | périodique=Discrete Applied Mathematics
 | volume=1 | numéro =3 | passage=209-215
 | année=1979
 | éditeur =Elsevier}}</ref>, alors qu'il existe un [[schéma d'approximation en temps polynomial]] pour le cas planaire<ref>
{{chapitre
 |auteur1 = David Eisenstat |auteur2= Philip N. Klein  |auteur3= Claire Mathieu
 |titre chapitre     = Approximating ''k''-center in planar graphs
 |titre ouvrage = Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014
 |passage     = 617-627
 |année     = 2014}}
</ref>.

Ce n'est pas le cas de tous les problèmes, par exemple le [[problème de couverture par sommets]] reste [[NP-complet]], c'est-à-dire difficile à résoudre a priori, même si l'on se restreint à des graphes planaires de [[Degré (théorie des graphes)|degré]] au plus 3<ref>{{Garey Johnson NP}}</ref>.

== Références ==
<references />

== Voir aussi ==
=== Articles connexes ===
* [[Graphe dual]]
* [[Théorème de Battle-Harary-Kodama]]
* [[Critère de planarité de Whitney]]
* [[Critère de planarité de Fraysseix-Rosenstiehl]]
* [[Critère de planarité de Mac Lane]]
* [[Invariant de Colin de Verdière|Critère de planarité de Colin de Verdière]]
* [[k-arbre]]
* [[Théorème du séparateur planaire]]
* [[Théorème de Fáry]] (représentation d'un graphe planaire avec des arêtes rectilignes)

=== Liens externes ===
* [http://pigale.sourceforge.net/ 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
* [http://neamar.fr/Res/BGraphe BGraphe] — pour jouer avec les graphes planaires

{{portail|mathématiques|informatique théorique}}
[[Catégorie:Concept en théorie des graphes|Planaire]]
[[Catégorie:Graphe géométrique]]
[[Catégorie:Graphe planaire|*]]