El criterio de planaridad de Whitney es una descripción matroide de gráficos planos . El criterio lleva el nombre de Hassler Whitney [1] . El criterio establece que un grafo G es plano si y solo si su matriz gráfica también es cográfica (es decir, es la matriz dual otra matriz gráfica).
En términos de teoría de grafos pura, este criterio puede formularse de la siguiente manera: debe existir otro grafo (dual) G '=( V ', E ') y una correspondencia biyectiva entre las aristas E ' y las aristas E del grafo original G tal que un subconjunto T de aristas E forma un árbol generador del grafo G si y sólo si las aristas correspondientes al complemento del conjunto E - T forman un árbol generador del grafo G '.
Hay otros criterios para la planaridad , por ejemplo, el teorema de Pontryagin-Kuratovsky .
Una forma equivalente del criterio de Whitney dice que un grafo G es plano si y solo si tiene un grafo dual cuya matroide gráfica es dual a la matroide gráfica de G. Un grafo cuya matroide gráfica es dual a la matroide gráfica de G se conoce como el dual algebraico de G. Entonces, el criterio de planaridad de Whitney se puede reformular de la siguiente manera: un gráfico es plano si y solo si tiene un gráfico dual algebraicamente.
Si un gráfico está incrustado en una superficie topológica, como un plano, de modo que cualquier cara incrustada sea un disco topológico, entonces el gráfico incrustado dual se define como un gráfico (en algunos casos, un multigrafo ) H que tiene un vértice para cada uno . cara empotrada y una arista para cada par de caras adyacentes. Según el criterio de Whitney, las siguientes condiciones son equivalentes:
Es posible definir gráficos duales de un gráfico incrustado en superficies no planas como un toro, pero estos gráficos duales generalmente no tienen la correspondencia con los cortes, ciclos y árboles de expansión requeridos por el criterio de Whitney.