En la teoría de grafos topológicos, un gráfico de 1 plano es un gráfico que se puede dibujar en el plano euclidiano de tal manera que cada borde tiene como máximo una intersección con solo otro borde.
Los gráficos de 1 plano fueron considerados por primera vez por Ringel, quien demostró que se pueden colorear con un máximo de siete colores [1] . Posteriormente, el número exacto de colores necesarios para colorear estos gráficos se redujo (en el peor de los casos) a seis [2] . Un ejemplo de un gráfico K 6 completo que es de 1 plano muestra que los gráficos de 1 plano a veces pueden requerir seis colores para colorear. Sin embargo, la prueba de la suficiencia de seis colores no es fácil.
La razón por la que Ringel consideró gráficos uniplanares fue un intento de resolver una variante del problema de coloración total para gráficos planos , en el que los vértices y las caras de un gráfico plano están coloreados de tal manera que no hay dos vértices adyacentes que tengan el mismo color. color y dos caras adyacentes cualesquiera también deben estar coloreadas en colores diferentes, los colores, así como los colores de los vértices y caras adyacentes a ellos, deben ser diferentes. Obviamente, esto se puede hacer con ocho colores si aplicamos el teorema de los cuatro colores para un gráfico y su gráfico dual por separado, utilizando dos conjuntos disjuntos de cuatro colores. Sin embargo, puede obtener menos colores si forma un gráfico auxiliar que tiene un vértice para cada vértice y cara del gráfico plano original, y en el que dos vértices del gráfico auxiliar son adyacentes si corresponden a objetos adyacentes del gráfico plano dado. . La coloración de los vértices del gráfico auxiliar corresponde a la coloración del gráfico plano original. El gráfico auxiliar es uniplanar, lo que significa que el problema de coloración de caras y vértices de Ringel se puede resolver usando seis colores [2] . El grafo K 6 no se puede obtener como grafo auxiliar de esta forma, pero sin embargo el problema de colorear vértices y caras a veces requiere seis colores. Por ejemplo, si coloreas el gráfico plano de un prisma triangular , sus 6 vértices + 5 caras requieren seis colores [3] .
Cualquier gráfico uniplano con n vértices tiene como máximo 4n − 8 aristas [4] . Más estrictamente, cada dibujo de un gráfico de 1 plano tiene como máximo n − 2 intersecciones . Quitar una arista de cada par de aristas que se cruzan deja un gráfico plano que tiene como máximo 3n − 6 aristas, lo que implica inmediatamente el límite de 4n − 8 aristas del gráfico uniplanar original [5] . Sin embargo, a diferencia de los gráficos planos (para los cuales todos los gráficos planos máximos en un conjunto dado de vértices tienen el mismo número de aristas), hay gráficos 1-planares máximos (gráficos a los que no se puede agregar un borde conservando la 1-planaridad) que tienen sustancialmente 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 gráfico uniplano se puede usar para mostrar que el gráfico completo K 7 con siete vértices no es uniplano, ya que este gráfico tiene 21 aristas, y luego 4 n − 8 = 20 < 21 [7] .
Se dice que un gráfico de 1 plano es un gráfico de 1 plano óptimo si tiene exactamente 4n − 8 aristas, el número máximo posible. En una incrustación de 1 plano de un gráfico óptimo de 1 plano, los bordes que no se cruzan necesariamente forman un mosaico en cuadriláteros (es decir, forman un gráfico poliédrico en el que cada cara es un cuadrilátero ). Cualquier cuadrante genera un gráfico de 1 plano al agregar dos diagonales a cada cara cuadrada. De ello se deduce que cualquier gráfico uniplano óptimo es euleriano (todos sus vértices tienen un grado par ), que el grado más pequeño en dichos gráficos es 6 y que cualquier gráfico uniplano óptimo tiene al menos ocho vértices con exactamente seis grados. Además, cualquier gráfico óptimo de 1 plano está conectado por 4 vértices , y cualquier sección de 4 vértices en dicho gráfico es un ciclo de corte en el cuadrilátero subyacente [8] .
Los gráficos que tienen dibujos rectilíneos de 1 plano (es decir, dibujos en los que cada borde está representado por un segmento de línea recta y cada segmento está intersecado por otro borde como máximo) tienen un límite ligeramente más fuerte de 4 n − 9 en el número máximo de bordes, que se logra en un número infinito de gráficos [9] .
Se conoce una clasificación completa de gráficos completos uniplanares , gráficos bipartitos completos y gráficos multipartitos completos más generales . Cualquier gráfico bipartito completo de la forma K 2, n es 1-planar, como lo es cualquier gráfico tripartito completo de la forma K 1,1, n . Además de estos conjuntos infinitos, los gráficos uniplanares 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 gráficos mínimos multipartitos completos que no son uniplanos 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 uniplano porque es un subgrafo de K 1,1,1,6 , pero K 3,7 no es uniplano [7] .
Comprobar si un gráfico es uniplano es NP-completo [10] [11] y el problema sigue siendo NP-completo incluso para gráficos obtenidos a partir de gráficos planos añadiendo un solo borde [12] y para gráficos de ancho acotado [ 13] .
El problema es fijo-paramétricamente solucionable si se parametriza por número ciclomático o profundidad de árbol , por lo que puede resolverse en tiempo polinomial si estos parámetros están limitados [13] .
A diferencia del teorema de Faree para gráficos planos, no todos los gráficos de 1 plano se pueden dibujar de 1 plano con segmentos de línea como bordes [14] [15] . Sin embargo, comprobar si se puede dibujar un gráfico de 1 plano con bordes rectos se puede hacer en tiempo polinomial [16] . Además, cualquier gráfico de 1 plano conectado con 3 vértices tiene un dibujo de 1 plano en el que, como máximo, un borde en la cara exterior tiene una torcedura . Tal dibujo se puede construir en tiempo lineal , basado en una incrustación de gráfico de 1 plano [17] . Los gráficos de 1 plano tienen un grosor de libro limitado [18] , pero algunos gráficos de 1 plano, incluido K 2,2,2,2 , tienen un grosor de libro de al menos cuatro [19] .
Los gráficos uniplanos tienen un ancho de árbol local acotado , lo que significa que existe una función (lineal) f tal que los gráficos uniplanos de diámetro d tienen un ancho de árbol como máximo f ( d ). La misma propiedad es válida para gráficos más generales que se pueden incrustar en una superficie de género acotado con un número acotado de cruces por borde. También tienen separadores , un pequeño conjunto de vértices cuya eliminación divide el gráfico en componentes conectados cuyo tamaño es una fracción constante del gráfico completo. Sobre la base de estas propiedades, numerosos algoritmos de gráficos planos, como la técnica de Brenda Sue Baker para construir algoritmos de aproximación , se pueden extender a gráficos de 1 plano. Por ejemplo, este método conduce a un esquema de tiempo polinomial aproximado para encontrar el conjunto independiente más grande de un gráfico de un plano [20] .
La clase de gráficos análoga a los gráficos planos exteriores para 1 planaridad se llama gráficos 1 planos exteriores . Estos son gráficos que se pueden dibujar en un disco con vértices en el límite del disco y con bordes que tienen como máximo una intersección por borde. Estos gráficos siempre se pueden dibujar (como un gráfico uniplanar externo) con bordes rectos e intersecciones en ángulo recto [21] . Usando programación dinámica en el árbol SPQR de un gráfico dado, es posible verificar si el gráfico es externamente uniplanar en tiempo lineal [22] [23] . Los componentes de gráficos triconectados (nodos de árbol SPQR) solo pueden consistir en ciclos , gráficos de enlaces y gráficos completos con cuatro vértices, lo que implica que los gráficos de un plano externo son planos y tienen un ancho de árbol de tres como máximo. A diferencia de los gráficos de 1 plano, los gráficos de 1 plano extrínsecos tienen una caracterización en términos de grafos menores : un gráfico es extrínseco de 1 plano si y solo si no contiene ninguno de los cinco menores prohibidos [23] .
La clase de gráficos de 1 plano incluye gráficos de 4 mapas , gráficos formados a partir de regiones adyacentes del plano con la condición de que ningún punto se encuentre en el borde de más de cuatro regiones (los vértices (regiones) están conectados por un borde si la frontera de las regiones). Por el contrario, cualquier gráfico óptimo de 1 plano es un gráfico de 4 mapas. Sin embargo, los gráficos de 1 plano que no son óptimos de 1 plano pueden no ser gráficos de mapa [24] .
Los gráficos 1-planares se generalizan a gráficos k - planares, en los que cada borde es cruzado por otros bordes como máximo k veces. Ringel definió el número de intersección local de un gráfico G como el k no negativo más pequeño tal que G tiene un dibujo k -planar. Dado que el número local de intersecciones es igual al mayor grado del gráfico de intersección de los bordes del patrón óptimo, y el grosor (el número mínimo de gráficos planos en los que se pueden descomponer los bordes) puede considerarse como el número cromático de el gráfico de intersección del patrón apropiado, del teorema de Brooks se deduce que el grosor es como máximo uno mayor que el número local de intersecciones [25] . Los gráficos k -planares con n vértices tienen un máximo de O ( k 1/2 n ) aristas [26] y un ancho de árbol de O (( kn ) 1/2 ) [27] . El menor superficial de un gráfico k -planar con profundidad d es en sí mismo ( 2d + 1) k -planar, por lo que los menores superficiales de los gráficos 1-planar y k -planar son gráficos dispersos , lo que significa aquí que 1-planar y k- los grafos planos tienen una extensión acotada [28] .
Para gráficos no planos, también puede establecer el número de parámetros de intersecciones , el número mínimo de bordes que se cruzan en cualquier dibujo de gráfico. Un gráfico con k intersecciones es necesariamente k -planar, pero lo contrario no es necesariamente cierto. Por ejemplo, el gráfico de Heawood tiene 3 intersecciones, pero estas intersecciones no tienen que ser con un borde, es de 1 plano y se puede dibujar con optimización simultánea del número total de intersecciones e intersecciones por un borde.
Otro concepto relacionado con los gráficos no planos es el sesgo , el número mínimo de bordes que deben eliminarse para hacer un gráfico plano.