En teoría de grafos topológicos , un grafo uniplanar es un grafo que se puede dibujar en el plano euclidiano de tal manera que cada arista tiene como máximo un punto de cruce, donde cruza una única arista adicional. Si un grafo uniplanar, una de las generalizaciones más naturales de los grafos planos , se dibuja de esa manera, el dibujo se denomina grafo uniplanar o incrustación uniplanar del grafo .
Los grafos uniplanares fueron estudiados por primera vez por Ringel (1965), quien demostró que se pueden colorear con siete colores como máximo. [1] Más tarde, se demostró que el número preciso de colores necesarios para colorear estos grafos, en el peor de los casos, era seis. [2] El ejemplo del grafo completo K 6 , que es uniplanar, muestra que los grafos uniplanares a veces pueden requerir seis colores. Sin embargo, la prueba de que seis colores siempre son suficientes es más complicada.
La motivación de Ringel fue tratar de resolver una variación de coloración total para grafos planares , en la que uno colorea simultáneamente los vértices y las caras de un grafo planar de tal manera que ningún par de vértices adyacentes tenga el mismo color, ninguna par de caras adyacentes tenga el mismo color, y ningún vértice y cara que sean adyacentes entre sí tengan el mismo color. Obviamente, esto se puede hacer usando ocho colores aplicando el teorema de los cuatro colores al grafo dado y su grafo dual por separado, usando dos conjuntos disjuntos de cuatro colores. Sin embargo, se pueden obtener menos colores formando un grafo auxiliar que tenga un vértice para cada vértice o cara del grafo planar dado, y en el que dos vértices del grafo auxiliar sean adyacentes siempre que correspondan a características adyacentes del grafo planar dado. Una coloración de vértice del grafo auxiliar corresponde a una coloración de vértice-cara del grafo planar original. Este grafo auxiliar es 1-planar, de lo que se deduce que el problema de coloración de vértice-cara de Ringel también se puede resolver con seis colores. [2] El grafo K 6 no puede formarse como un grafo auxiliar de esta manera, pero sin embargo el problema de coloración de vértices y caras también requiere a veces seis colores; por ejemplo, si el grafo planar que se va a colorear es un prisma triangular , entonces sus once vértices y caras requieren seis colores, porque no se puede dar un solo color a tres de ellos. [3]
Cada grafo 1-planar con n vértices tiene como máximo 4 n − 8 aristas. [4] Más fuertemente, cada dibujo 1-planar tiene como máximo n − 2 cruces ; quitando una arista de cada par de aristas que se cruzan queda un grafo planar, que puede tener como máximo 3 n − 6 aristas, de las cuales se sigue inmediatamente el límite de 4 n − 8 en el número de aristas en el grafo 1-planar original. [5] Sin embargo, a diferencia de los grafos planares (para los cuales todos los grafos planares maximales en un conjunto de vértices dado tienen el mismo número de aristas entre sí), existen grafos 1-planares maximales (grafos a los cuales no se pueden agregar aristas adicionales mientras se preserva la 1-planaridad) que tienen significativamente menos de 4 n − 8 aristas. [6] El límite de 4 n − 8 en el número máximo posible de aristas en un grafo uniplanar se puede utilizar para demostrar que el grafo completo K 7 en siete vértices no es uniplanar, porque este grafo tiene 21 aristas y en este caso 4 n − 8 = 20 < 21. [7]
Se dice que un grafo uniplanar es un grafo uniplanar óptimo si tiene exactamente 4 n − 8 aristas, el máximo posible. En una incrustación uniplanar de un grafo uniplanar óptimo, las aristas no cruzadas forman necesariamente una cuadrangulación (un grafo poliédrico en el que cada cara es un cuadrilátero ). Toda cuadrangulación da lugar a un grafo uniplanar óptimo de esta manera, añadiendo las dos diagonales a cada una de sus caras cuadriláteras. De ello se deduce que todo grafo uniplanar óptimo es euleriano (todos sus vértices tienen grado par ), que el grado mínimo en un grafo de este tipo es seis y que todo grafo uniplanar óptimo tiene al menos ocho vértices de grado exactamente seis. Además, todo grafo uniplanar óptimo está conexo por 4 vértices y cada corte de 4 vértices en un grafo de este tipo es un ciclo de separación en la cuadrangulación subyacente. [8]
Los gráficos que tienen dibujos rectos uniplanares (es decir, dibujos en los que cada borde está representado por un segmento de línea, y en los que cada segmento de línea es atravesado como máximo por otro borde) tienen un límite ligeramente más estricto de 4 n − 9 en el número máximo de bordes, logrado por un número infinito de gráficos. [9]
Se conoce una clasificación completa de los grafos completos 1-planares , grafos bipartitos completos y, de forma más general, grafos multipartitos completos . Todo grafo bipartito completo de la forma K 2, n es 1-planar (incluso planar), al igual que todo grafo tripartito completo de la forma K 1,1, n . Aparte de estos conjuntos infinitos de ejemplos, los únicos grafos 1-planares multipartitos completos son K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1,1,1,2,2 y sus subgrafos. Los grafos multipartitos completos no 1-planares mínimos son K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 y K 1,1,1,1,3 . Por ejemplo, el grafo bipartito completo K 3,6 es 1-planar porque es un subgrafo de K 1,1,1,6 , pero K 3,7 no es 1-planar. [7]
Es NP-completo probar si un gráfico dado es 1-planar, [10] [11] y sigue siendo NP-completo incluso para los gráficos formados a partir de gráficos planares agregando un solo borde [12] y para gráficos de ancho de banda acotado . [13] El problema es manejable con parámetros fijos cuando se parametriza por número ciclomático o por profundidad de árbol , por lo que se puede resolver en tiempo polinomial cuando esos parámetros están acotados. [13]
A diferencia del teorema de Fáry para grafos planares, no todos los grafos uniplanares pueden dibujarse uniplanarmente con segmentos de línea recta como aristas. [14] [15] Sin embargo, comprobar si un dibujo uniplanar puede enderezarse de esta manera se puede hacer en tiempo polinomial . [16] Además, cada grafo uniplanar conexo con 3 vértices tiene un dibujo uniplanar en el que como máximo una arista, en la cara exterior del dibujo, tiene una curva . Este dibujo se puede construir en tiempo lineal a partir de una incrustación uniplanar del grafo. [17] Los grafos uniplanares tienen un grosor de libro acotado , [18] pero algunos grafos uniplanares, incluidos K 2,2,2,2, tienen un grosor de libro de al menos cuatro. [19]
Los grafos uniplanares tienen un ancho de árbol local acotado , lo que significa que existe una función (lineal) f tal que los grafos uniplanares de diámetro d tienen un ancho de árbol como máximo f ( d ); la misma propiedad se cumple de manera más general para los grafos que se pueden incrustar en una superficie de género acotado con un número acotado de cruces por arista. También tienen separadores , pequeños conjuntos de vértices cuya eliminación descompone el grafo en componentes conectados cuyo tamaño es una fracción constante del tamaño del grafo completo. Con base en estas propiedades, numerosos algoritmos para grafos uniplanares, como la técnica de Baker para diseñar algoritmos de aproximación , se pueden extender a grafos uniplanares. Por ejemplo, este método conduce a un esquema de aproximación de tiempo polinomial para el conjunto independiente máximo de un grafo uniplanar. [20]
La clase de grafos análogos a los grafos externalplanares para 1-planaridad se denominan grafos external-1-planares . Estos son grafos que se pueden dibujar en un disco, con los vértices en el límite del disco y con como máximo un cruce por arista. Estos grafos siempre se pueden dibujar (de manera external-1-planar) con aristas rectas y cruces en ángulo recto . [21] Al usar programación dinámica en el árbol SPQR de un grafo dado, es posible probar si es external-1-planar en tiempo lineal . [22] [23] Los componentes triconectados del grafo (nodos del árbol SPQR) pueden consistir solo en grafos de ciclo , grafos de enlace y grafos completos de cuatro vértices , de lo que también se deduce que los grafos external-1-planares son planares y tienen un ancho de árbol de como máximo tres.
Los grafos uniplanares incluyen los grafos de 4 mapas , grafos formados a partir de las adyacencias de regiones en el plano con, como máximo, cuatro regiones que se encuentran en cualquier punto. Por el contrario, todo grafo uniplanar óptimo es un grafo de 4 mapas. Sin embargo, los grafos uniplanares que no son 1-planares óptimos pueden no ser grafos de mapas. [24]
Los grafos 1-planares se han generalizado a grafos k -planares, grafos para los cuales cada arista se cruza como máximo k veces (los grafos 0-planares son exactamente los grafos planares). Ringel definió el número de cruce local de G como el menor entero no negativo k tal que G tenga un dibujo k -planar. Debido a que el número de cruce local es el grado máximo del grafo de intersección de las aristas de un dibujo óptimo, y el grosor (número mínimo de grafos planares en los que se pueden dividir las aristas) puede verse como el número cromático de un grafo de intersección de un dibujo apropiado, se deduce del teorema de Brooks que el grosor es como máximo uno más el número de cruce local. [25] Los grafos k -planares con n vértices tienen como máximo O ( k 1/2 n ) aristas, [26] y ancho de árbol O (( kn ) 1/2 ). [27] Un menor superficial de un grafo k -planar, con profundidad d , es en sí mismo un grafo k -planar (2 d + 1) , por lo que los menores superficiales de grafos 1-planares y de grafos k -planares también son grafos dispersos , lo que implica que los grafos 1-planares y k -planares tienen expansión acotada . [28]
Los grafos no planos también pueden parametrizarse por su número de cruces , el número mínimo de pares de aristas que se cruzan en cualquier dibujo del grafo. Un grafo con número de cruces k es necesariamente k -planar, pero no necesariamente al revés. Por ejemplo, el grafo de Heawood tiene número de cruces 3, pero no es necesario que sus tres cruces ocurran todos en la misma arista del grafo, por lo que es 1-planar, y de hecho puede dibujarse de una manera que optimice simultáneamente el número total de cruces y los cruces por arista.
Otro concepto relacionado con los gráficos no planos es la asimetría del gráfico , el número mínimo de aristas que deben eliminarse para que un gráfico sea plano.