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). 

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

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

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

Articles liés 
 Test de planarité
 Test de planarité gauche-droite
 Théorie des matroïdes

Graphe planaire
Combinatoire
Algorithmique