Critère de planarité de Whitney

En mathématiques, et plus particulièrement en théorie des graphes, le critère de planarité de Whitney est une caractérisation, en théorie des matroïdes, des graphes planaires ; critère nommée d'après Hassler Whitney. Il affirme qu'un graphe G est planaire si et seulement si son matroïde graphique est également cographique (c'est-à-dire qu'il est le matroïde dual d'un autre matroïde graphique).

Un graphe planaire et son dual. Chaque cycle dans le graphe bleu est une coupe minimale dans le graphe rouge, et vice versa, donc les deux graphes sont des duaux algébriques et ont des matroïdes graphiques duaux.

En termes de théorie des graphes pures, ce critère énonce comme suit :

Un graphe $G=(V,E)$ est planaire si et seulement s'il existe un autre graphe $G'=(V',E')$, appelé le dual, et une correspondance bijective entre $E'$ et $E$ telle qu'un sous-ensemble $T$ de $E$ forme un arbre couvrant de $G$ si et seulement si les arêtes correspondantes au sous-ensemble complémentaire $E-T$ forment un arbre couvrant de $G'$.

Dual algébrique

Une formulation équivalente du critère de Whitney est :

Un graphe G est planaire si et seulement s'il a un graphe dual dont le matroïde graphique est dual du matroïde graphique de G.

Un graphe dont le matroïde graphique est le dual du matroïde graphique de G est appelé dual algébrique de G. Ainsi, le critère de planarité de Whitney peut être exprimé simplement comme suit :

Un graphe est planaire si et seulement s'il possède un dual algébrique.

Dual topologique

Si un graphe G est plongé dans une surface topologique telle que le plan, de sorte que chaque face du plongement est un disque topologique, le dual graphique du plongement est défini comme le graphe (ou dans certains cas le multigraphe) H qui a un sommet pour chaque face du plongement de G et une arête pour chaque paire de faces adjacentes. Selon le critère de Whitney, les conditions suivantes sont équivalentes :

• La surface sur laquelle le plongement existe est topologiquement équivalente au plan, à la sphère ou à la sphère trouée ;
• H est un dual algébrique de G ;
• chaque cycle simple de G correspond à une coupe minimale de H, et vice versa ;
• chaque cycle simple de H correspond à une coupe minimale de G, et vice versa ;
• chaque arbre couvrant de G correspond au complément d'un arbre couvrant de H, et vice versa.

Il est possible de définir des graphes duaux de graphes plongés sur des surfaces non planes telles que le tore, mais ces duaux ne vérifient en général pas la correspondance entre coupes, cycles et arbres couvrant requis par le critère de Whitney.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Whitney's planarity criterion » (voir la liste des auteurs).

Articles liés

• Test de planarité
• Test de planarité gauche-droite
• Théorie des matroïdes