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 un punto de cruce, donde cruza un solo borde adicional. Si un gráfico de 1 plano, una de las generalizaciones más naturales de los gráficos de plano , se dibuja de esa manera, el dibujo se denomina gráfico de 1 plano o incrustación de 1 plano del gráfico .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/38/3-crossing_Heawood_graph.svg/220px-3-crossing_Heawood_graph.svg.png)
Colorante
Las gráficas de 1 plano fueron estudiadas por primera vez por Ringel (1965) , quien demostró que se pueden colorear con un máximo de siete colores. [1] Más tarde, se demostró que el número exacto de colores necesarios para colorear estos gráficos, en el peor de los casos, era de seis. [2] El ejemplo del gráfico completo K 6 , que es de 1 plano, muestra que los gráficos de 1 plano a veces pueden requerir seis colores. Sin embargo, la prueba de que seis colores siempre son suficientes es más complicada.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/0/04/Prism-vf-color.svg/220px-Prism-vf-color.svg.png)
La motivación de Ringel fue tratar de resolver una variación de coloración total para gráficos planos , en la que uno colorea simultáneamente los vértices y las caras de un gráfico plano de tal manera que no hay dos vértices adyacentes que tengan el mismo color, no hay dos caras adyacentes que tengan el mismo color. color, y ningún vértice y cara adyacentes entre sí tienen el mismo color. Obviamente, esto se puede hacer usando ocho colores aplicando el teorema de los cuatro colores al gráfico dado y su gráfico dual por separado, usando dos conjuntos disjuntos de cuatro colores. Sin embargo, se pueden obtener menos colores formando un gráfico auxiliar que tenga un vértice para cada vértice o cara del gráfico plano dado, y en el que dos vértices de gráfico auxiliar sean adyacentes siempre que correspondan a características adyacentes del gráfico plano dado. Una coloración de vértice del gráfico auxiliar corresponde a una coloración de cara de vértice del gráfico plano original. Este gráfico auxiliar es 1-plano, de lo que se sigue que el problema de coloración del vértice-cara de Ringel también se puede resolver con seis colores. [2] El gráfico K 6 no puede formarse como un gráfico auxiliar de esta manera, pero sin embargo, el problema de coloración del vértice-cara a veces también requiere seis colores; por ejemplo, si el gráfico plano 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]
Densidad de bordes
Cada gráfico de 1 plano con n vértices tiene como máximo 4 n - 8 aristas. [4] Más claramente, cada dibujo de 1 plano tiene como máximo n - 2 cruces ; la eliminación de una arista de cada par de aristas que se cruzan deja un gráfico plano, que puede tener como máximo 3 n - 6 aristas, a partir de las cuales sigue inmediatamente el límite de 4 n - 8 en el número de aristas del gráfico 1 plano original. [5] Sin embargo, a diferencia de las gráficas planas (para las cuales todas las gráficas planas máximas en un conjunto de vértices dado tienen el mismo número de aristas), existen gráficas planas máximas (gráficas a las que no se pueden agregar aristas adicionales mientras se 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 gráfico de 1 plano se puede utilizar para mostrar que el gráfico completo K 7 en siete vértices no es 1 plano, porque este gráfico tiene 21 aristas y en este caso 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 4 n - 8 aristas, el máximo posible. En una incrustación de 1 plano de un gráfico de 1 plano óptimo, los bordes no cruzados forman necesariamente una cuadrangulación (un gráfico poliédrico en el que cada cara es un cuadrilátero ). Cada cuadrangulación da lugar a un gráfico 1-planar óptimo de esta manera, sumando las dos diagonales a cada una de sus caras cuadriláteras. De ello se deduce que todo gráfico 1-plano óptimo es euleriano (todos sus vértices tienen grados pares ), que el grado mínimo en dicho gráfico es seis y que todo gráfico 1-plano óptimo tiene al menos ocho vértices de grado exactamente seis. Además, cada gráfico 1-planar óptimo está conectado con 4 vértices , y cada corte de 4 vértices en dicho gráfico es un ciclo de separación en la cuadrangulación subyacente. [8]
Los gráficos que tienen dibujos rectos de 1 plano (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 está atravesado como máximo por otro borde) tienen un límite ligeramente más estrecho de 4 n - 9 en el número máximo de aristas, logrado por un número infinito de gráficos. [9]
Gráficos multipartitos completos
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a0/1planar-K2222.svg/300px-1planar-K2222.svg.png)
Se conoce una clasificación completa de los gráficos completos de 1 plano , los gráficos bipartitos completos y, en general, los gráficos multipartitos completos . Todo gráfico bipartito completo de la forma K 2, n es 1-plano, al igual que todo gráfico tripartito completo de la forma K 1,1, n . Aparte de estos conjuntos infinitos de ejemplos, las únicas gráficas planas 1 multipartitas completas 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. Las gráficas multipartitas completas no planas mínimas 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-plano porque es un subgrafo de K 1,1,1,6 , pero K 3,7 no es 1-plano. [7]
Complejidad computacional
Es NP-completo para probar si un gráfico dado es 1-planar, [10] [11] y permanece NP-completo incluso para los gráficos formados a partir de gráficos planos 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 puede resolverse en tiempo polinómico cuando esos parámetros están acotados. [13]
En contraste con el teorema de Fáry para gráficas planas, no todas las gráficas 1-planar pueden dibujarse 1-planar con segmentos de línea recta para sus bordes. [14] [15] Sin embargo, probar si un dibujo de un plano se puede enderezar de esta manera se puede hacer en tiempo polinomial . [16] Además, cada gráfico de 1 plano conectado a 3 vértices tiene un dibujo de 1 plano en el que como máximo un borde, en la cara exterior del dibujo, tiene una curva . Este dibujo se puede construir en tiempo lineal a partir de una incrustación de 1 plano del gráfico. [17] Los gráficos de 1 plano tienen un grosor de libro acotado , [18] pero algunos gráficos de 1 plano que incluyen K 2,2,2,2 tienen un grosor de libro de al menos cuatro. [19]
Los gráficos de 1 plano tienen un ancho de árbol local acotado , lo que significa que hay una función (lineal) f tal que los gráficos de 1 plano de diámetro d tienen un ancho de árbol como máximo f ( d ); la misma propiedad se aplica de manera más general a los gráficos que se pueden incrustar en una superficie de género acotado con un número acotado de cruces por borde. También tienen separadores , pequeños conjuntos de vértices cuya eliminación descompone el gráfico en componentes conectados cuyo tamaño es una fracción constante del tamaño del gráfico completo. Con base en estas propiedades, numerosos algoritmos para gráficos planos, como la técnica de Baker para diseñar algoritmos de aproximación , pueden extenderse a gráficos de 1 plano. Por ejemplo, este método conduce a un esquema de aproximación de tiempo polinomial para el conjunto máximo independiente de un gráfico de 1 plano. [20]
La clase de gráficas análogas a las gráficas planas externas para 1 planaridad se denominan gráficas planas externas 1 . Estos son gráficos 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 borde. Estos gráficos siempre se pueden dibujar (de una manera exterior 1 plana) con bordes rectos y cruces en ángulo recto . [21] Mediante el uso de programación dinámica en el árbol SPQR de un gráfico dado, es posible probar si es exterior-1-planar en tiempo lineal . [22] [23] Los componentes triconectados de la gráfica (nodos del árbol SPQR) pueden consistir solo en gráficas de ciclo , gráficas de enlace y gráficas completas de cuatro vértices , de las cuales también se deduce que las gráficas externas 1 planas son planas y tener un ancho de árbol como máximo tres.
Los gráficos de 1 plano incluyen los gráficos de 4 mapas , gráficos formados a partir de las adyacencias de regiones en el plano con un máximo de cuatro regiones que se encuentran en cualquier punto. Por el contrario, todo gráfico 1 planar óptimo 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]
Las gráficas 1-planar se han generalizado a k gráficas planas, gráficas para las cuales cada borde se cruza como máximo k veces (las gráficas planas 0 son exactamente las gráficas planas). Ringel definió el número de cruce local de G como el menor entero no negativo k tal que G tiene un dibujo k -planar. Debido a que el número de cruce local es el grado máximo del gráfico de intersección de los bordes de un dibujo óptimo, y el grosor (número mínimo de gráficos planos en los que se pueden dividir los bordes) puede verse como el número cromático de un gráfico de intersección de un dibujo apropiado, se sigue del teorema de Brooks que el espesor es como máximo uno más el número de cruce local. [25] Las k -gráficas planas con n vértices tienen como máximo O ( k 1/2 n ) aristas, [26] y un ancho de árbol O (( kn ) 1/2 ). [27] Un menor superficial de un gráfico k -planar, con profundidad d , es en sí mismo un gráfico (2 d + 1) k -planar, por lo que los menores superficiales de los gráficos 1-planar y de k -planar también son gráficos dispersos , lo que implica que las gráficas 1-planar y k -planar tienen expansión acotada . [28]
Los gráficos no planos también se pueden parametrizar por su número de cruce , el número mínimo de pares de bordes que se cruzan en cualquier dibujo del gráfico. Un gráfico con el número de cruce k es necesariamente k -planar, pero no necesariamente al revés. Por ejemplo, el gráfico de Heawood tiene el número de cruce 3, pero no es necesario que sus tres cruces ocurran en el mismo borde del gráfico, por lo que es 1-plano y, de hecho, se puede dibujar de una manera que optimice simultáneamente el número total de cruces y los cruces por borde.
Otro concepto relacionado para las gráficas no planas es la asimetría de la gráfica , el número mínimo de aristas que deben eliminarse para hacer una gráfica plana.
Referencias
- ↑ Ringel, Gerhard (1965), "Ein Sechsfarbenproblem auf der Kugel", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (en alemán), 29 (1-2): 107-117, doi : 10.1007 / BF02996313 , MR 0187232 , S2CID 123286264.
- ^ a b Borodin, OV (1984), "Solución del problema de Ringel sobre coloración vértice-cara de gráficas planas y coloración de gráficas 1-planas", Metody Diskretnogo Analiza (41): 12-26, 108, MR 0832128.
- ^ Albertson, Michael O .; Mohar, Bojan (2006), "Colorear vértices y caras de gráficos localmente planos" (PDF) , Graphs and Combinatorics , 22 (3): 289–295, doi : 10.1007 / s00373-006-0653-4 , MR 2264852 , S2CID 1028234.
- ^ Schumacher, H. (1986), "Zur Struktur 1-planarer Graphen", Mathematische Nachrichten (en alemán), 125 : 291–300, doi : 10.1002 / mana.19861250122 , MR 0847368.
- ^ Czap, Július; Hudák, Dávid (2013), "Sobre dibujos y descomposiciones de gráficos 1-planar" , Electronic Journal of Combinatorics , 20 (2), P54, doi : 10.37236 / 2392.
- ^ Brandeburgo, Franz Josef; Eppstein, David ; Gleißner, Andreas; Goodrich, Michael T .; Hanauer, Kathrin; Reislhuber, Josef (2013), "Sobre la densidad de grafos 1-planar máximos", en Didimo, Walter; Patrignani, Maurizio (eds.), Proc. 20 ° Int. Symp. Dibujo Gráfico.
- ^ a b Czap, Július; Hudák, Dávid (2012), "1-planaridad de gráficos multipartitos completos", Matemáticas aplicadas discretas , 160 (4–5): 505–512, doi : 10.1016 / j.dam.2011.11.014 , MR 2876333.
- ^ Suzuki, Yusuke (2010), "Reincorporaciones de gráficos de 1 plano máximo", SIAM Journal on Discrete Mathematics , 24 (4): 1527-1540, doi : 10.1137 / 090746835 , MR 2746706.
- ^ Didimo, Walter (2013), "Density of straight-line 1-planar graph drawings", Information Processing Letters , 113 (7): 236–240, doi : 10.1016 / j.ipl.2013.01.013 , MR 3017985.
- ^ Grigoriev, Alejandro; Bodlaender, Hans L. (2007), "Algoritmos para gráficos incrustables con pocos cruces por borde", Algorithmica , 49 (1): 1–11, doi : 10.1007 / s00453-007-0010-x , hdl : 1874/17980 , Señor 2344391 , S2CID 8174422.
- ^ Korzhik, Vladimir P .; Mohar, Bojan (2009), "Obstrucciones mínimas para inmersiones 1 y prueba de dureza de planaridad 1", en Tollis, Ioannis G .; Patrignani, Maurizio (eds.), Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Creta, Grecia, 21-24 de septiembre de 2008, Revised Papers , Lecture Notes in Computer Science , 5417 , Springer, págs. 302–312, arXiv : 1110.4881 , doi : 10.1007 / 978-3-642-00219-9_29 , S2CID 13436158.
- ^ Cabello, Sergio; Mohar, Bojan (2012), Agregar un borde a los gráficos planos dificulta el cruce del número y la planaridad 1 , arXiv : 1203.5944 , Bibcode : 2012arXiv1203.5944C. Versión ampliada de un artículo del 17 ° Simposio de ACM sobre geometría computacional, 2010.
- ^ a b Bannister, Michael J .; Cabello, Sergio; Eppstein, David (2013), "Complejidad parametrizada de 1-planaridad", Simposio de algoritmos y estructuras de datos (WADS 2013) , arXiv : 1304.5591 , Bibcode : 2013arXiv1304.5591B , doi : 10.7155 / jgaa.00457 , S2CID 4417962.
- ^ Eggleton, Roger B. (1986), "Dibujos rectilíneos de gráficos", Utilitas Mathematica , 29 : 149-172, MR 0846198.
- ^ Thomassen, Carsten (1988), "Dibujos rectilíneos de gráficos", Journal of Graph Theory , 12 (3): 335–341, doi : 10.1002 / jgt.3190120306 , MR 0956195.
- ^ Hong, Seok-Hee; Eades, Peter ; Liotta, Giuseppe; Poon, Sheung-Hung (2012), "Teorema de Fáry para gráficos 1-planar", en Gudmundsson, Joachim; Mestre, Julián; Viglas, Taso (eds.), Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, 20-22 de agosto de 2012, Proceedings , Lecture Notes in Computer Science, 7434 , Springer, págs. 335–346, doi : 10.1007 / 978-3-642-32241-9_29.
- ^ Alam, Md. Jawaherul; Brandeburgo, Franz J .; Kobourov, Stephen G. (2013), "Dibujos de cuadrícula de línea recta de gráficos de 1 plano conectados en 3", Dibujo de gráfico: 21º Simposio Internacional, GD 2013, Burdeos, Francia, 23 al 25 de septiembre de 2013, Artículos seleccionados revisados ( PDF) , Lecture Notes in Computer Science, 8242 , págs. 83–94, doi : 10.1007 / 978-3-319-03841-4_8.
- ^ Bekos, Michael A .; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "Los gráficos 1-planar tienen un grosor de libro constante", Algoritmos - ESA 2015 , Lecture Notes in Computer Science, 9294 , Springer, págs. 130-141, doi : 10.1007 / 978-3-662-48350 -3_12.
- ^ Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "El libro que integra el problema desde una perspectiva de resolución de SAT", Proc. 23º Simposio Internacional sobre Dibujo de Gráficos y Visualización de Redes (GD 2015) , págs. 113–125.
- ^ Grigoriev y Bodlaender (2007) . Grigoriev y Bodlaender establecen sus resultados solo para gráficos con una incrustación 1-planar conocida, y utilizan una descomposición de árbol de una planarización de la incrustación con cruces reemplazados por vértices de grado cuatro; sin embargo, sus métodos implican directamente el ancho de árbol local acotado del gráfico 1-plano original, lo que permite que el método de Baker se aplique directamente a él sin conocer la incrustación.
- ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), "Cada gráfico de un plano exterior tiene un dibujo de cruce en ángulo recto", International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi : 10.1142 / S021819591250015X , MR 3042921.
- ^ Hong, Seok-Hee; Eades, Peter ; Katoh, Naoki; Liotta, Giuseppe; Schweitzer, Pascal; Suzuki, Yusuke (2013), "Un algoritmo de tiempo lineal para probar la planaridad 1 externa", en Wismath, Stephen; Wolff, Alexander (eds.), 21st International Symposium, GD 2013, Burdeos, Francia, 23-25 de septiembre de 2013, Revised Selected Papers , Lecture Notes in Computer Science, 8242 , págs. 71–82, doi : 10.1007 / 978- 3-319-03841-4_7.
- ^ Auer, Christopher; Bachmaier, Christian; Brandeburgo, Franz J .; Gleißner, Andreas; Hanauer, Kathrin; Neuwirth, Daniel; Reislhuber, Josef (2013), "Reconociendo grafos 1-planar externos en tiempo lineal", en Wismath, Stephen; Wolff, Alexander (eds.), 21st International Symposium, GD 2013, Bordeaux, France, 23-25 de septiembre de 2013, Revised Selected Papers , Lecture Notes in Computer Science, 8242 , pp. 107-118, doi : 10.1007 / 978- 3-319-03841-4_10.
- ^ Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM , 49 (2): 127-138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819 , S2CID 2657838.
- ^ Kainen, Paul (1973), "Grosor y tosquedad de los gráficos", Abh. Matemáticas. Sem. Univ. Hamburgo , 39 : 88–95, doi : 10.1007 / BF02992822 , MR 0335322 , S2CID 121667358.
- ^ Pach, János ; Tóth, Géza (1997), "Gráficos dibujados con pocos cruces por borde", Combinatorica , 17 (3): 427–439, doi : 10.1007 / BF01215922 , MR 1606052 , S2CID 20480170.
- ^ Dujmović, Vida; Eppstein, David ; Wood, David R. (2015), "Género, ancho de árbol y número de cruce local", Proc. 23º Simposio Internacional sobre Dibujo de Gráficos y Visualización de Redes (GD 2015) , págs. 77–88, arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D.
- ^ Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, Teorema 14.4, p. 321, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
Otras lecturas
- Kobourov, Stephen; Liotta, Giuseppe; Montecchiani, Fabrizio (2017), "Una bibliografía anotada sobre 1-planaridad", Computer Science Review , 25 : 49–67, arXiv : 1703.02261 , Bibcode : 2017arXiv170302261K , doi : 10.1016 / j.cosrev.2017.06.002 , S2CID 7732463