Cubierta plana

En teoría de grafos , una cubierta planar de un grafo finito G es un grafo de recubrimiento finito de G que es a su vez un grafo planar . Todo grafo que puede incrustarse en el plano proyectivo tiene una cubierta planar; una conjetura sin resolver de Seiya Negami afirma que estos son los únicos grafos con cubiertas planas. ^{[ 1 ]}

La existencia de una cubierta planar es una propiedad de grafo cerrado bajo menores ^{[ 2 ]} y , por lo tanto, puede caracterizarse por un número finito de menores prohibidos , pero se desconoce el conjunto exacto de menores prohibidos. Por la misma razón, existe un algoritmo de tiempo polinomial para comprobar si un grafo dado tiene una cubierta planar, pero se desconoce una descripción explícita de este algoritmo.

Una aplicación de recubrimiento de un grafo C a otro grafo H puede describirse mediante una función f de los vértices de C a los vértices de H que, para cada vértice v de C , da una biyección entre los vecinos de v y los vecinos de f ( v ). ^{[ 3 ]} Si H es un grafo conexo , cada vértice de H debe tener el mismo número de preimágenes en C ; ^{[ 2 ]} este número se llama ply de la aplicación, y C se llama un grafo de recubrimiento de G . Si C y H son ambos finitos, y C es un grafo planar , entonces C se llama un recubrimiento planar de H .

El grafo del dodecaedro posee una simetría que asigna cada vértice a su vértice antipodal. El conjunto de pares de vértices antipodales y sus adyacencias puede considerarse un grafo, el grafo de Petersen . El dodecaedro forma una cubierta plana de este grafo no planar. ^{[ 4 ]} Como muestra este ejemplo, no todo grafo con una cubierta plana es planar. Sin embargo, cuando un grafo planar cubre uno no planar, el número de capas debe ser par . ^{[ 5 ]}

El grafo de un prisma k -gonal tiene 2k vértices y es planar con dos caras k -gonales y k caras cuadriláteras. Si k = ab , con a ≥ 2 y b ≥ 3, entonces tiene una aplicación de recubrimiento de a capas para un prisma b -gonal, en la que dos vértices del prisma k se mapean al mismo vértice del prisma b si ambos pertenecen a la misma cara k -gonal y la distancia entre ellos es un múltiplo de b . Por ejemplo, el prisma dodecagonal puede formar un recubrimiento de 2 capas para el prisma hexagonal , un recubrimiento de 3 capas para el cubo o un recubrimiento de 4 capas para el prisma triangular . Estos ejemplos muestran que un grafo puede tener muchos recubrimientos planares diferentes y puede ser el recubrimiento planar para muchos otros grafos. Además, muestran que el número de capas de un recubrimiento planar puede ser arbitrariamente grande. No son las únicas cubiertas que involucran prismas: por ejemplo, el prisma hexagonal también puede cubrir un grafo no planar, el grafo de utilidad K _3,3 , identificando pares de vértices antipodales. ^{[ 6 ]}       

Si un grafo H tiene una cubierta planar, también la tiene cada grafo menor de H. ^{[ 2 ]} Un menor G de H se puede formar eliminando aristas y vértices de H y contrayendo aristas de H. El grafo de cobertura C se puede transformar de la misma manera: para cada arista o vértice eliminado en H , se elimina su preimagen en C , y para cada arista o vértice contraído en H , se contrae su preimagen en C. El resultado de aplicar estas operaciones a C es un menor de C que cubre G. Dado que cada menor de un grafo planar es a su vez planar, esto da una cubierta planar del menor G.

Debido a que los grafos con recubrimientos planares son cerrados bajo la operación de tomar menores, se deduce del teorema de Robertson-Seymour que pueden caracterizarse por un conjunto finito de menores prohibidos . ^{[ 7 ]} Un grafo es un menor prohibido para esta propiedad si no tiene recubrimiento planar, pero todos sus menores sí lo tienen. Esta caracterización puede usarse para probar la existencia de un algoritmo de tiempo polinomial que comprueba la existencia de un recubrimiento planar, buscando cada uno de los menores prohibidos y devolviendo que existe un recubrimiento planar solo si esta búsqueda no encuentra ninguno de ellos. ^{[ 8 ]} Sin embargo, debido a que se desconoce el conjunto exacto de menores prohibidos para esta propiedad, esta prueba de existencia no es constructiva y no conduce a una descripción explícita del conjunto de menores prohibidos ni del algoritmo basado en ellos. ^{[ 9 ]}

Otra operación gráfica que preserva la existencia de una cubierta planar es la transformación Y-Δ , que reemplaza cualquier vértice de grado tres de un grafo H por un triángulo que conecta sus tres vecinos. ^{[ 2 ]} Sin embargo, la inversa de esta transformación, una transformación Δ-Y, no necesariamente preserva las cubiertas planares.

Además, la unión disjunta de dos grafos que tienen cubiertas también tendrá una cubierta, formada como la unión disjunta de los grafos que las contienen. Si las dos cubiertas tienen la misma capa, esta también será la capa de su unión.

Si un grafo H tiene una incrustación en el plano proyectivo , entonces necesariamente tiene un recubrimiento planar, dado por la preimagen de H en el recubrimiento doble orientable del plano proyectivo, que es una esfera. Negami (1986) demostró, a la inversa, que si un grafo conexo H tiene un recubrimiento planar de dos capas, entonces H debe tener una incrustación en el plano proyectivo. ^{[ 10 ]} La suposición de que H es conexo es necesaria aquí, porque una unión disjunta de grafos proyectivo-planares puede no ser en sí misma proyectivo-planar ^{[ 11 ]} pero aún así tendrá un recubrimiento planar, la unión disjunta de los recubrimientos dobles orientables.

Una cubierta regular de un grafo H es aquella que proviene de un grupo de simetrías de su grafo de cubierta: las preimágenes de cada vértice en H son una órbita del grupo. Negami (1988) demostró que todo grafo conexo con una cubierta regular planar puede incrustarse en el plano proyectivo. ^{[ 12 ]} Basándose en estos dos resultados, conjeturó que, de hecho, todo grafo conexo con una cubierta planar es proyectivo. ^{[ 13 ]} Hasta 2013, esta conjetura seguía sin resolverse. ^{[ 14 ]} También se la conoce como la "conjetura 1-2-∞" de Negami, porque puede reformularse afirmando que el ply mínimo de una cubierta planar, si existe, debe ser 1 o  2. ^{[ 15 ]}

Al igual que los grafos con recubrimientos planares, los grafos con incrustaciones planares proyectivas pueden caracterizarse por menores prohibidos. En este caso, se conoce el conjunto exacto de menores prohibidos: hay 35 de ellos. 32 de estos son conexos, y uno de estos 32 grafos aparece necesariamente como un menor en cualquier grafo conexo no proyectivo-planar. ^{[ 16 ]} Desde que Negami hizo su conjetura, se ha demostrado que 31 de estos 32 menores prohibidos o bien no tienen recubrimientos planares, o bien pueden reducirse mediante transformaciones Y-Δ a un grafo más simple de esta lista. ^{[ 17 ]} El único grafo restante para el que esto aún no se ha hecho es K _{1,2,2,2 , un} grafo de vértice de siete vértices que forma el esqueleto de una pirámide octaédrica de cuatro dimensiones . Si se pudiera demostrar que K _1,2,2,2 no tiene ningún recubrimiento planar, esto completaría una demostración de la conjetura. Por otro lado, si la conjetura es falsa, K _1,2,2,2 sería necesariamente su contraejemplo más pequeño . ^{[ 18 ]}

Una conjetura relacionada de Michael Fellows , ahora resuelta, se refiere a los emuladores planares , una generalización de los recubrimientos planares que mapea vecindarios de grafos sobreyectivamente en lugar de biyectivamente. ^{[ 19 ]} Los grafos con emuladores planares, como aquellos con recubrimientos planares, son cerrados bajo menores y transformaciones Y-Δ. ^{[ 20 ]} En 1988, independientemente de Negami, Fellows conjeturó que los grafos con emuladores planares son exactamente los grafos que pueden incrustarse en el plano proyectivo. ^{[ 21 ]} La conjetura es cierta para emuladores regulares , provenientes de automorfismos del grafo de recubrimiento subyacente, por un resultado análogo al resultado de Negami (1988) para recubrimientos planares regulares. ^{[ 22 ]} Sin embargo, varios de los 32 menores prohibidos conexos para grafos proyectivo-planares resultan tener emuladores planares. ^{[ 23 ]} Por lo tanto, la conjetura de Fellows es falsa. Encontrar un conjunto completo de menores prohibidos para la existencia de emuladores planares sigue siendo un problema abierto . ^{[ 24 ]}