Incrustaciones sin enlaces

En la teoría topológica de grafos , una disciplina matemática, una incrustación sin enlaces de un grafo no dirigido es una incrustación del grafo en el espacio euclidiano tridimensional de tal manera que no haya dos ciclos del grafo enlazados. Una incrustación plana es una incrustación con la propiedad de que cada ciclo es el borde de un disco topológico cuyo interior es disjunto del grafo. Un grafo incrustable sin enlaces es un grafo que tiene una incrustación sin enlaces o plana; estos grafos forman un análogo tridimensional de los grafos planares . ^{[ 1 ]} Complementariamente, un grafo intrínsecamente enlazado es un grafo que no tiene una incrustación sin enlaces.

Las incrustaciones planas son automáticamente sin enlaces, pero no al revés. ^{[ 2 ]} El grafo completo K ₆ , el grafo de Petersen y los otros cinco grafos de la familia de Petersen no tienen incrustaciones sin enlaces. ^{[ 1 ]} Todo menor de un grafo incrustable sin enlaces es también incrustable sin enlaces, ^{[ 3 ]} al igual que todo grafo al que se puede llegar desde un grafo incrustable sin enlaces mediante transformaciones YΔ y ΔY . ^{[ 2 ]} Los grafos incrustables sin enlaces tienen a los grafos de la familia de Petersen como sus menores prohibidos , ^{[ 4 ]} e incluyen los grafos planares y los grafos de ápice . ^{[ 2 ]} Se pueden reconocer, y se puede construir una incrustación plana para ellos, en O ( n ² ) . ^{[ 5 ]}

Cuando un círculo se proyecta en el espacio euclidiano tridimensional mediante una función inyectiva (una función continua que no proyecta dos puntos distintos del círculo en el mismo punto del espacio), su imagen es una curva cerrada . Dos curvas cerradas disjuntas que se encuentran en el mismo plano se denominan no vinculadas , y, de forma más general, se dice que un par de curvas cerradas disjuntas no están vinculadas cuando existe una deformación continua del espacio que las mueve a ambas al mismo plano, sin que ninguna de las curvas pase por la otra ni por sí misma. Si no existe tal movimiento continuo, se dice que las dos curvas están vinculadas . Por ejemplo, el enlace de Hopf está formado por dos círculos que pasan cada uno por el disco generado por el otro. Constituye el ejemplo más simple de un par de curvas vinculadas, pero es posible que las curvas se vinculen de otras maneras más complejas. Si dos curvas no están vinculadas, entonces es posible encontrar un disco topológico en el espacio, que tenga a la primera curva como su frontera y sea disjunto de la segunda. Por el contrario, si existe tal disco, entonces las curvas están necesariamente desvinculadas.

El número de enlace de dos curvas cerradas en el espacio tridimensional es un invariante topológico de las curvas: es un número, definido a partir de las curvas de varias maneras equivalentes, que no cambia si las curvas se mueven continuamente sin pasar una por la otra. La versión del número de enlace utilizada para definir incrustaciones sin enlaces de grafos se obtiene proyectando la incrustación sobre el plano y contando el número de cruces de la incrustación proyectada en las que la primera curva pasa por encima de la segunda, módulo 2. ^{[ 2 ]} La proyección debe ser "regular", lo que significa que ningún par de vértices se proyecta al mismo punto, ningún vértice se proyecta al interior de una arista, y en cada punto de la proyección donde se intersecan las proyecciones de dos aristas, se cruzan transversalmente ; con esta restricción, cualquier par de proyecciones conduce al mismo número de enlace. El número de enlace de la no vinculación es cero, y por lo tanto, si un par de curvas tiene un número de enlace distinto de cero, las dos curvas deben estar vinculadas. Sin embargo, existen ejemplos de curvas que están vinculadas pero que tienen un número de vinculación cero, como el enlace de Whitehead .

Una incrustación de un grafo en el espacio tridimensional consiste en una correspondencia entre los vértices del grafo y los puntos en el espacio, y entre las aristas del grafo y las curvas en el espacio, de manera que cada extremo de cada arista se corresponda con un extremo de la curva correspondiente, y de manera que las curvas de dos aristas diferentes no se intersequen excepto en un extremo común. Cualquier grafo finito tiene un número finito (aunque quizás exponencial) de ciclos simples distintos , y si el grafo se incrusta en el espacio tridimensional, cada uno de estos ciclos forma una curva cerrada simple. Se puede calcular el número de enlace de cada par de curvas disjuntas formadas de esta manera; si todos los pares de ciclos tienen un número de enlace de cero, se dice que la incrustación es sin enlaces. ^{[ 6 ]}

En algunos casos, un grafo puede estar incrustado en el espacio de tal manera que, para cada ciclo del grafo, se puede encontrar un disco delimitado por ese ciclo que no atraviese ninguna otra característica del grafo. En este caso, el ciclo debe estar desvinculado de todos los demás ciclos disjuntos a él en el grafo. Se dice que la incrustación es plana si cada ciclo delimita un disco de esta manera. ^{[ 7 ]} Una incrustación plana es necesariamente sin enlaces, pero pueden existir incrustaciones sin enlaces que no sean planas: por ejemplo, si G es un grafo formado por dos ciclos disjuntos, y está incrustado para formar el enlace de Whitehead, entonces la incrustación es sin enlaces pero no plana.

Se dice que un grafo está intrínsecamente vinculado si, independientemente de cómo se incruste, la incrustación siempre está vinculada. Aunque las incrustaciones sin vínculos y las incrustaciones planas no son lo mismo, los grafos que tienen incrustaciones sin vínculos son iguales a los grafos que tienen incrustaciones planas. ^{[ 8 ]}

Como demostró Sachs (1983) , cada uno de los siete grafos de la familia de Petersen está intrínsecamente vinculado: independientemente de cómo se incruste cada uno de estos grafos en el espacio, tienen dos ciclos que están vinculados entre sí. Estos grafos incluyen el grafo completo K ₆ , el grafo de Petersen , el grafo formado al eliminar una arista del grafo bipartito completo K _4,4 , y el grafo tripartito completo K _3,3,1 .

Todo grafo planar tiene una incrustación plana y sin enlaces: basta con incrustar el grafo en un plano e incrustar el plano en el espacio. Si un grafo es planar, esta es la única forma de incrustarlo de forma plana y sin enlaces en el espacio: toda incrustación plana puede deformarse continuamente para quedar sobre un plano. Y, a la inversa, todo grafo no planar sin enlaces tiene múltiples incrustaciones sin enlaces. ^{[ 2 ]}

Un grafo de vértice , formado al añadir un único vértice a un grafo planar, también tiene una incrustación plana y sin enlaces: se incrusta la parte planar del grafo en un plano, se coloca el vértice sobre el plano y se dibujan las aristas desde el vértice hasta sus vecinos como segmentos de línea. Cualquier curva cerrada dentro del plano delimita un disco debajo del plano que no pasa por ninguna otra característica del grafo, y cualquier curva cerrada que pase por el vértice delimita un disco encima del plano que no pasa por ninguna otra característica del grafo. ^{[ 2 ]}

Si un grafo tiene una incrustación plana o sin enlaces, entonces modificar el grafo subdividiendo o dessubdividiendo sus aristas, agregando o eliminando múltiples aristas entre el mismo par de puntos, y realizando transformaciones YΔ y ΔY que reemplazan un vértice de grado tres por un triángulo que conecta sus tres vecinos o viceversa, preserva la planitud y la ausencia de enlaces. ^{[ 2 ]} En particular, en un grafo planar cúbico (uno en el que todos los vértices tienen exactamente tres vecinos, como el cubo) es posible hacer duplicados de cualquier conjunto independiente de vértices realizando una transformación YΔ, agregando múltiples copias de las aristas triangulares resultantes y luego realizando las transformaciones ΔY inversas.

Si un grafo G tiene una incrustación sin enlaces o plana, entonces cada menor de G (un grafo formado por la contracción de aristas y la eliminación de aristas y vértices) también tiene una incrustación sin enlaces o plana. Las eliminaciones no pueden destruir la planitud de una incrustación, y una contracción se puede realizar dejando un extremo de la arista contraída en su lugar y redirigiendo todas las aristas incidentes al otro extremo a lo largo del camino de la arista contraída. Por lo tanto, según el teorema de Robertson-Seymour , los grafos incrustables sin enlaces tienen una caracterización de grafo prohibido como los grafos que no contienen ninguno de un conjunto finito de menores. ^{[ 3 ]}

El conjunto de menores prohibidos para los grafos incrustables sin enlaces fue identificado por Sachs (1983) : los siete grafos de la familia Petersen son todos grafos intrínsecamente enlazados mínimos en menores. Sin embargo, Sachs no pudo demostrar que estos fueran los únicos grafos enlazados mínimos, y esto fue finalmente logrado por Robertson, Seymour y Thomas (1995) .

La caracterización menor prohibida de los grafos sin enlaces conduce a un algoritmo de tiempo polinomial para su reconocimiento, pero no para construir realmente una incrustación. Kawarabayashi, Kreutzer y Mohar (2010) describieron un algoritmo de tiempo lineal que prueba si un grafo es incrustable sin enlaces y, de ser así, construye una incrustación plana del grafo. Su algoritmo encuentra subgrafos planares grandes dentro del grafo dado tales que, si existe una incrustación sin enlaces, debe respetar la incrustación plana del subgrafo. Al simplificar repetidamente el grafo cada vez que se encuentra dicho subgrafo, reducen el problema a uno en el que el grafo restante tiene ancho de árbol acotado , en cuyo punto puede resolverse mediante programación dinámica .

El problema de comprobar eficientemente si una incrustación dada es plana o no enlazada fue planteado por Robertson, Seymour y Thomas (1993a) . Sigue sin resolverse y su complejidad es equivalente a la del problema de desanudar , que consiste en comprobar si una única curva en el espacio no está anudada. ^{[ 5 ]} Se sabe que comprobar la ausencia de nudos (y, por lo tanto, también la ausencia de enlaces de una incrustación) pertenece a NP , pero no se sabe que sea NP-completo . ^{[ 9 ]}

La cuestión de si K ₆ tiene una incrustación sin enlaces o plana fue planteada dentro de la comunidad de investigación topológica a principios de la década de 1970 por Bothe (1973) . Las incrustaciones sin enlaces fueron presentadas a la comunidad de teoría de grafos por Horst Sachs ( 1983 ) , quien planteó varios problemas relacionados, incluido el problema de encontrar una caracterización de grafos prohibida para los grafos con incrustaciones sin enlaces y planas; Sachs demostró que los siete grafos de la familia Petersen (incluido K ₆ ) no tienen tales incrustaciones. Como observaron Nešetřil y Thomas (1985) , los grafos incrustables sin enlaces son cerrados bajo menores de grafos , de lo cual se deduce por el teorema de Robertson-Seymour que existe una caracterización de grafos prohibida. La demostración de la existencia de un conjunto finito de grafos de obstrucción no conduce a una descripción explícita de este conjunto de menores prohibidos, pero de los resultados de Sachs se deduce que los siete grafos de la familia Petersen pertenecen a dicho conjunto. Estos problemas fueron finalmente resueltos por Robertson, Seymour y Thomas (1995) ^{[ 18 ]} , quienes demostraron que los siete grafos de la familia Petersen son los únicos menores prohibidos mínimos para estos grafos. Por lo tanto, los grafos incrustables sin enlaces y los grafos incrustables planos constituyen el mismo conjunto de grafos, y son idénticos a los grafos que no poseen un menor de la familia Petersen. 

Sachs (1983) también solicitó cotas para el número de aristas y el número cromático de grafos incrustables sin enlaces. El número de aristas en un grafo sin enlaces de n vértices es como máximo 4 n − 10: los grafos de ápice máximos con n > 4 tienen exactamente esta cantidad de aristas, ^{[ 1 ]} y Mader (1968) demostró una cota superior correspondiente en la clase más general de grafos libres de K _{6 -menores.} Nešetřil y Thomas (1985) observaron que la pregunta de Sachs sobre el número cromático se resolvería mediante una demostración de la conjetura de Hadwiger de que cualquier grafo k -cromático tiene como menor un grafo completo de k vértices. La demostración de Robertson, Seymour y Thomas (1993c) del caso k = 6 de la conjetura de Hadwiger es suficiente para resolver la pregunta de Sachs: los grafos sin enlaces pueden colorearse con como máximo cinco colores, ya que cualquier grafo 6-cromático contiene un menor K ₆ y no es sin enlaces, y existen grafos sin enlaces como K ₅ que requieren cinco colores. El teorema de snark implica que todo grafo cúbico incrustable sin enlaces es 3-arista-coloreable .      

Los incrustaciones sin enlaces comenzaron a estudiarse dentro de la comunidad de investigación de algoritmos a finales de la década de 1980 a través de los trabajos de Fellows y Langston (1988) y Motwani, Raghunathan y Saran (1988) . Algorítmicamente, el problema de reconocer grafos incrustables planos y sin enlaces se resolvió una vez que se demostró la caracterización de menores prohibidos: un algoritmo de Robertson y Seymour (1995) puede usarse para probar en tiempo polinomial si un grafo dado contiene alguno de los siete menores prohibidos. ^{[ 19 ]} Este método no construye incrustaciones sin enlaces o planas cuando existen, pero van der Holst (2009) desarrolló un algoritmo que sí construye una incrustación , y Kawarabayashi, Kreutzer y Mohar (2010) encontraron un algoritmo de tiempo lineal más eficiente .

Una pregunta final de Sachs (1983) sobre la posibilidad de un análogo del teorema de Fáry para grafos sin enlaces parece no haber sido respondida: ¿cuándo la existencia de una incrustación sin enlaces o plana con aristas curvas o lineales a trozos implica la existencia de una incrustación sin enlaces o plana en la que las aristas son segmentos de línea recta ?