En la teoría de grafos topológicos , una disciplina matemática, una incrustación sin vínculos de una gráfica no dirigida es una incrustación de la gráfica en un espacio euclidiano tridimensional de tal manera que no hay dos ciclos de la gráfica vinculados. Una incrustación plana es una incrustación con la propiedad de que cada ciclo es el límite de un disco topológico cuyo interior está separado del gráfico. Un gráfico incrustable sin vínculos es un gráfico que tiene una incrustación plana o sin vínculos; estos gráficos forman un análogo tridimensional de los gráficos planos . [1] De forma complementaria, un gráfico intrínsecamente vinculado es un gráfico que no tiene una inserción sin enlaces.
Las incrustaciones planas son automáticamente sin enlaces, pero no al revés. [2] El gráfico completo K 6 , el gráfico de Petersen y los otros cinco gráficos de la familia Petersen no tienen incrustaciones sin enlaces. [1] Cada gráfico menor de un gráfico incrustable sin vínculos es nuevamente incrustable sin vínculos, [3] al igual que todos los gráficos que se pueden alcanzar desde un gráfico incrustable sin vínculos mediante una transformada Y-Δ . [2] Los gráficos integrables sin enlaces tienen los gráficos de la familia Petersen como sus menores prohibidos , [4] e incluyen los gráficos planos y los gráficos de vértice . [2] Pueden ser reconocidos, y se puede construir una incrustación plana para ellos, en. [5]
Definiciones
Cuando el círculo se asigna al espacio euclidiano tridimensional mediante una función inyectiva (una función continua que no asigna dos puntos diferentes del círculo al mismo punto del espacio), su imagen es una curva cerrada . Dos curvas cerradas disjuntas que se encuentran en el mismo plano están desvinculadas , y más generalmente se dice que un par de curvas cerradas disjuntas están desvinculadas cuando hay una deformación continua del espacio que las mueve a ambas hacia el mismo plano, sin que ninguna de las curvas pase a través de ellas. el otro o por sí mismo. Si no existe tal movimiento continuo, se dice que las dos curvas están vinculadas . Por ejemplo, el enlace Hopf está formado por dos círculos que pasan cada uno por el disco atravesado por el otro. Constituye el ejemplo más simple de un par de curvas vinculadas, pero es posible que las curvas estén vinculadas de otras formas más complicadas. Si dos curvas no están vinculadas, entonces es posible encontrar un disco topológico en el espacio, teniendo la primera curva como su límite y disjunto de la segunda curva. Por el contrario, si existe un disco de este tipo, las curvas están necesariamente desvinculadas.
El número de enlace de dos curvas cerradas en un espacio tridimensional es un invariante topológico de las curvas: es un número, definido a partir de las curvas en cualquiera de varias formas equivalentes, que no cambia si las curvas se mueven continuamente sin pasar por cada una de ellas. otro. La versión del número de enlace utilizado para definir las incrustaciones sin enlaces de gráficos se encuentra proyectando la incrustación en el plano y contando el número de cruces de la incrustación proyectada en la que la primera curva pasa sobre la segunda, módulo 2. [2] El la proyección debe ser "regular", es decir, que no se proyecten dos vértices hacia el mismo punto, ningún vértice se proyecte hacia el interior de una arista, y en cada punto de la proyección donde se cruzan las proyecciones de dos aristas, se cruzan transversalmente ; con esta restricción, dos proyecciones cualesquiera conducen al mismo número de enlace. El número de enlace de la desvinculació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, hay ejemplos de curvas que están vinculadas pero que tienen un número de vinculación cero, como el vínculo de Whitehead .
Una incrustación de un gráfico en un espacio tridimensional consiste en un mapeo desde los vértices del gráfico hasta los puntos en el espacio, y desde los bordes del gráfico hasta las curvas en el espacio, de modo que cada punto final de cada borde se mapea a un punto final de la curva correspondiente, y de tal manera que las curvas de dos aristas diferentes no se crucen excepto en un punto final común de las aristas. Cualquier gráfico finito tiene un número finito (aunque quizás exponencial) de ciclos simples distintos , y si el gráfico está incrustado en un espacio tridimensional, entonces 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 cero, se dice que la incrustación no tiene enlace. [6]
En algunos casos, un gráfico puede estar incrustado en el espacio de tal manera que, para cada ciclo del gráfico, se puede encontrar un disco delimitado por ese ciclo que no cruza ninguna otra característica del gráfico. En este caso, el ciclo debe estar desvinculado de todos los demás ciclos separados de él en el gráfico. 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 vínculos, pero puede haber incrustaciones sin vínculos que no son planas: por ejemplo, si G es un gráfico formado por dos ciclos disjuntos y está incrustado para formar el enlace de Whitehead, entonces la incrustación es sin vínculos pero no plano.
Se dice que un gráfico está intrínsecamente vinculado si, sin importar cómo esté incrustado, la incrustación siempre está vinculada. Aunque las incrustaciones sin enlaces y planas no son lo mismo, los gráficos que tienen incrustaciones sin enlaces son los mismos que los gráficos que tienen incrustaciones planas. [8]
Ejemplos y contraejemplos
Como mostró Sachs (1983) , cada uno de los siete gráficos de la familia Petersen está intrínsecamente vinculado: no importa cómo cada uno de estos gráficos esté incrustado en el espacio, tienen dos ciclos que están vinculados entre sí. Estos gráficos incluyen el gráfico completo K 6 , el gráfico de Petersen , el gráfico formado al eliminar un borde del gráfico bipartito completo K 4,4 y el gráfico tripartito completo K 3,3,1 .
Cada gráfico plano tiene una incrustación plana y sin enlaces: simplemente incruste el gráfico en un plano e incruste el plano en el espacio. Si un gráfico es plano, esta es la única forma de incrustarlo de forma plana y sin vínculos en el espacio: cada incrustación plana se puede deformar continuamente para quedar en un plano plano. Y a la inversa, todos los gráficos sin enlaces no planos tienen múltiples incrustaciones sin enlaces. [2]
Un gráfico de vértice , formado al agregar un único vértice a un gráfico plano, también tiene una incrustación plana y sin enlaces: incruste la parte plana del gráfico en un plano, coloque el vértice sobre el plano y dibuje los bordes desde el vértice hasta su vecinos como segmentos de línea. Cualquier curva cerrada dentro del plano limita un disco debajo del plano que no pasa por ninguna otra característica gráfica, y cualquier curva cerrada a través del vértice limita un disco por encima del plano que no pasa por ninguna otra característica gráfica. [2]
Si un gráfico tiene una incrustación plana o sin vínculos, entonces modifique el gráfico subdividiendo o anulando la subdivisión de sus bordes, agregando o quitando múltiples bordes entre el mismo par de puntos y realizando transformaciones Y-Δ que reemplazan un vértice de grado tres por un triángulo que conecta sus tres vecinos o el reverso conservan la planitud y la falta de enlaces. [2] En particular, en un grafo plano 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 transformaciones Y-Δ, agregando múltiples copias de los bordes del triángulo resultante, y luego realizar las transformadas Δ-Y inversas.
Caracterización y reconocimiento
Si un gráfico G tiene una incrustación sin enlaces o plana, entonces cada menor de G (un gráfico formado por contracción de aristas y 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 se puede realizar una contracción dejando un punto final del borde contraído en su lugar y redireccionando todos los bordes incidentes al otro punto final a lo largo de la trayectoria del borde contraído. Por lo tanto, según el teorema de Robertson-Seymour , los gráficos incrustables sin enlaces tienen una caracterización gráfica prohibida como los gráficos que no contienen ninguno de un conjunto finito de menores. [3]
Sachs (1983) identificó el conjunto de menores prohibidos para los gráficos incrustables sin enlaces : los siete gráficos de la familia Petersen son todos gráficos menores-mínimos intrínsecamente vinculados. Sin embargo, Sachs no pudo probar que estos eran los únicos gráficos vinculados mínimos, y esto finalmente lo lograron Robertson, Seymour y Thomas (1995) .
La caracterización menor prohibida de los gráficos sin enlaces conduce a un algoritmo de tiempo polinomial para su reconocimiento, pero no para construir realmente una incrustación. Kawarabayashi, Kreutzer & Mohar (2010) describieron un algoritmo de tiempo lineal que prueba si un gráfico se puede incrustar sin enlaces y, de ser así, construye una incrustación plana del gráfico. Su algoritmo encuentra grandes subgrafos planos dentro del gráfico dado, de modo que, si existe una incrustación sin enlaces, debe respetar la incrustación plana del subgrafo. Al simplificar repetidamente el gráfico cada vez que se encuentra un subgráfico de este tipo, reducen el problema a uno en el que el gráfico restante tiene un ancho de árbol limitado , en cuyo punto se puede resolver mediante programación dinámica .
Robertson, Seymour y Thomas (1993a) plantearon el problema de comprobar eficazmente si una inserción determinada es plana o sin enlaces . Sigue sin resolverse y es equivalente en complejidad al problema de desanudar , el problema de probar si una sola curva en el espacio está desanudada. [5] Se sabe que la prueba de la ausencia de nudos (y, por lo tanto, también la prueba de la ausencia de enlaces de una incrustación) está en NP, pero no se sabe que sea NP completa . [9]
Familias relacionadas de gráficos
El invariante gráfico de Colin de Verdière es un número entero definido para cualquier gráfico que utilice la teoría de grafos algebraica . Los gráficos con el gráfico de Colin de Verdière invariante como máximo μ, para cualquier constante fija μ, forman una familia menor cerrada, y los primeros son bien conocidos: los gráficos con μ ≤ 1 son los bosques lineales (uniones disjuntas de rutas), las gráficas con μ ≤ 2 son las gráficas planas externas y las gráficas con μ ≤ 3 son las gráficas planas . Como conjeturaron Robertson, Seymour y Thomas (1993a) y Lovász y Schrijver (1998) demostraron, los gráficos con μ ≤ 4 son exactamente los gráficos incrustables sin enlaces.
Los gráficos planos y los gráficos de vértice se pueden incrustar sin vínculos, al igual que los gráficos obtenidos por transformaciones Y-Δ a partir de estos gráficos. [2] Los gráficos YΔY reducibles son los gráficos que se pueden reducir a un solo vértice mediante transformadas Y-Δ, eliminación de vértices aislados y vértices de grado uno y compresión de vértices de grado dos; también son cerradas menores e incluyen todas las gráficas planas. Sin embargo, existen gráficos sin enlaces que no son YΔY reducibles, como el gráfico de vértice formado al conectar un vértice de vértice a cada vértice de grado tres de un dodecaedro rómbico . [10] También existen gráficos sin enlaces que no se pueden transformar en un gráfico de vértice mediante transformaciones Y-Δ, eliminación de vértices aislados y vértices de grado uno, y compresión de vértices de grado dos: por ejemplo, el gráfico de corona de diez vértices tiene una incrustación sin enlaces, pero no se puede transformar en un gráfico de vértice de esta manera. [2]
Relacionado con el concepto de incrustación sin enlaces está el concepto de incrustación sin nudos , una incrustación de un gráfico de tal manera que ninguno de sus ciclos simples forma un nudo no trivial . Los gráficos que no tienen incrustaciones sin nudos (es decir, están intrínsecamente anudados ) incluyen K 7 y K 3,3,1,1 . [11] Sin embargo, también existen menores prohibidos mínimos para incrustaciones sin nudos que no se forman (como estos dos gráficos) agregando un vértice a un gráfico intrínsecamente vinculado. [12]
También se pueden definir familias de grafos por la presencia o ausencia de nudos y enlaces más complejos en sus incrustaciones, [13] o por incrustaciones sin eslabones en variedades tridimensionales distintas del espacio euclidiano. [14] Flapan, Naimi y Pommersheim (2001) definen una incrustación de grafos como triple enlace si hay tres ciclos ninguno de los cuales puede separarse de los otros dos; muestran que K 9 no está intrínsecamente triple ligado, pero K 10 sí lo es. [15] Más generalmente, se puede definir un n = Conectado incrustación para cualquier n sea una incrustación que contiene un n enlace -component que no puede ser separada por una esfera topológica en dos partes separadas; Los gráficos menores-mínimos que están intrínsecamente ligados a n son conocidos para todos los n . [dieciséis]
Historia
La cuestión de si K 6 tiene una incrustación plana o sin enlaces fue planteada dentro de la comunidad de investigación de topología a principios de la década de 1970 por Bothe (1973) . Horst Sachs ( 1983 ) llamó la atención de la comunidad de la teoría de grafos sobre las incrustaciones sin enlaces, incluido el problema de encontrar una caracterización gráfica prohibida de las gráficas con incrustaciones planas y sin enlaces; Sachs demostró que las siete gráficas de la familia Petersen (incluida la K 6 ) no tienen tales incrustaciones. Como observaron Nešetřil y Thomas (1985) , los gráficos incrustables sin enlaces se cierran bajo los gráficos menores , de lo que se deduce del teorema de Robertson-Seymour que existe una caracterización de gráficos prohibida. La prueba de la existencia de un conjunto finito de gráficos de obstrucción no conduce a una descripción explícita de este conjunto de menores prohibidos, pero de los resultados de Sachs se desprende que los siete gráficos de la familia Petersen pertenecen al conjunto. Estos problemas fueron finalmente resueltos por Robertson, Seymour & Thomas (1995) , [17] quienes demostraron que los siete gráficos de la familia Petersen son los únicos menores mínimos prohibidos para estos gráficos. Por lo tanto, los gráficos incrustables sin enlaces y los gráficos incrustables planos son el mismo conjunto de gráficos y son iguales a los gráficos que no tienen menores de la familia Petersen.
Sachs (1983) también solicitó límites en el número de bordes y el número cromático de gráficos incrustables sin enlaces. El número de aristas en un gráfico sin enlace n- vértice es como máximo 4 n - 10: los gráficos de vértice máximo con n > 4 tienen exactamente esta cantidad de aristas, [1] y Mader (1968) demostró un límite superior coincidente en la clase más general de K 6 -graficos libres de menores. Nešetřil y Thomas (1985) observaron que la pregunta de Sachs sobre el número cromático se resolvería mediante una prueba de la conjetura de Hadwiger de que cualquier gráfico k -cromático tiene como menor un gráfico k -vertex completo. La demostración de Robertson, Seymour & Thomas (1993c) del caso k = 6 de la conjetura de Hadwiger es suficiente para resolver la pregunta de Sachs: los gráficos sin enlaces pueden colorearse con un máximo de cinco colores, ya que cualquier gráfico 6-cromático contiene un K 6 minor y no sin enlaces, y existen gráficos sin enlaces como K 5 que requieren cinco colores. El teorema de snark implica que cada grafo incrustable sin enlaces cúbicos es coloreable en 3 bordes .
Las incrustaciones sin enlaces comenzaron a estudiarse dentro de la comunidad de investigación de algoritmos a fines de la década de 1980 a través de los trabajos de Fellows & Langston (1988) y Motwani, Raghunathan & Saran (1988) . Algorítmicamente, el problema de reconocer grafos incrustables planos y sin enlaces se resolvió una vez que se probó la caracterización menor prohibida: se puede usar un algoritmo de Robertson y Seymour (1995) para probar en tiempo polinómico si un grafo dado contiene alguno de los siete menores prohibidos. [18] Este método no construye incrustaciones planas o sin enlaces cuando existen, pero un algoritmo que construye una incrustación fue desarrollado por van der Holst (2009) , y Kawarabayashi, Kreutzer & Mohar ( 2009) encontraron un algoritmo de tiempo lineal más eficiente ( 2010) .
Una pregunta final de Sachs (1983) sobre la posibilidad de un análogo del teorema de Fáry para gráficos sin vínculos parece no haber sido respondida: ¿cuándo la existencia de una incrustación plana o sin vínculos con bordes lineales curvos o por partes implica la existencia de un incrustación plana en la que los bordes son segmentos de línea recta ?
Ver también
- Nudos y gráficos
Notas
- ↑ a b c Sachs (1983) .
- ↑ a b c d e f g h i Robertson, Seymour y Thomas (1993a) .
- ↑ a b Nešetřil y Thomas (1985)
- ^ Robertson, Seymour y Thomas (1995) .
- ↑ a b Kawarabayashi, Kreutzer y Mohar (2010)
- ^ Conway y Gordon (1983) ; Sachs (1983) ; Robertson, Seymour y Thomas (1993a) .
- ^ Robertson, Seymour y Thomas (1993a) . Una definición similar de "buena integración" aparece en Motwani, Raghunathan y Saran (1988) ; véase también Saran (1989) y Böhme (1990) .
- ^ Robertson, Seymour y Thomas (1993b) .
- ^ Hass, Lagarias y Pippenger (1999) .
- ^ Truemper (1992) .
- ^ Conway y Gordon (1983) ; Foisy (2002) .
- ^ Foisy (2003) .
- ^ Nešetřil y Thomas (1985) ; Fleming y Diesl (2005) .
- ^ Flapan y col. (2006)
- ^ Para obtener ejemplos adicionales de gráficos intrínsecamente triple enlazados, consulte Bowlin y Foisy (2004) .
- ^ Flapan y col. (2001)
- ^ Como ya lo anunciaron Robertson, Seymour & Thomas (1993b) .
- ^ La aplicación del algoritmo de Robertson-Seymour a este problema fue notada por Fellows & Langston (1988) .
Referencias
- Böhme, Thomas (1990), "Sobre representaciones espaciales de gráficos", en Bodendieck, Rainer (ed.), Métodos contemporáneos en teoría de gráficos: en honor al profesor Dr. Klaus Wagner , Mannheim: Bibliographisches Institut, Wissenschaftsverlag, págs. 151 –167, ISBN 978-3-411-14301-6. Según lo citado por Robertson, Seymour y Thomas (1993a) .
- Bothe, H.-G. (1973), "Problema P855", Coloquio Mathematicum , 28 : 163, Nuevo libro escocés, Problema 876, 20.5.1972. Como lo cita Sachs (1983) .
- Bowlin, Garry; Foisy, Joel (2004), "Algunos nuevos gráficos intrínsecamente ligados a 3" (PDF) , Journal of Knot Theory and its Ramifications , 13 (8): 1021-1028, doi : 10.1142 / S0218216504003652.
- Conway, John H .; Gordon, Cameron McA. (1983), "Nudos y vínculos en gráficos espaciales", Journal of Graph Theory , 7 (4): 445–453, doi : 10.1002 / jgt.3190070410.
- Becarios, Michael R .; Langston, Michael A. (1988), "Herramientas no constructivas para probar la decidibilidad en tiempo polinomial", Journal of the ACM , 35 (3): 727–739, doi : 10.1145 / 44483.44491.
- Flapan, Erica ; Howards, Hugh; Lawrence, Don; Mellor, Blake (2006), "Enlace intrínseco y anudado de gráficos en tres variedades arbitrarias", Topología algebraica y geométrica , 6 : 1025-1035, arXiv : math / 0508004 , doi : 10.2140 / agt.2006.6.1025.
- Flapan, Erica ; Naimi, Ramin; Pommersheim, James (2001), "Gráficos completos intrínsecamente triple enlazados" (PDF) , Topología y sus aplicaciones , 115 (2): 239–246, doi : 10.1016 / S0166-8641 (00) 00064-X.
- Flapan, Erica ; Pommersheim, James; Foisy, Joel; Naimi, Ramin (2001), "Gráficos intrínsecamente ligados a n", Journal of Knot Theory and Its Ramifications , 10 (8): 1143-1154, doi : 10.1142 / S0218216501001360.
- Fleming, Thomas; Diesl, Alexander (2005), "Gráficos intrínsecamente vinculados e incluso números de vinculación", Topología algebraica y geométrica , 5 : 1419–1432, arXiv : math / 0511133 , doi : 10.2140 / agt.2005.5.1419.
- Foisy, Joel (2002), "Gráficos intrínsecamente anudados", Journal of Graph Theory , 39 (3): 178–187, doi : 10.1002 / jgt.10017.
- Foisy, Joel (2003), "Un gráfico anudado intrínsecamente reconocido recientemente", Journal of Graph Theory , 43 (3): 199-209, doi : 10.1002 / jgt.10114.
- Hass, Joel ; Lagarias, Jeffrey C .; Pippenger, Nicholas (1999), "La complejidad computacional de los problemas de nudos y enlaces", Journal of the ACM , 46 (2): 185-211, arXiv : math / 9807016 , doi : 10.1145 / 301970.301971.
- van der Holst, Hein (2009), "Un algoritmo de tiempo polinómico para encontrar una incrustación sin enlaces de un gráfico", Journal of Combinatorial Theory, Serie B , 99 (2): 512–530, doi : 10.1016 / j.jctb. 2008.10.002.
- Kawarabayashi, Ken-ichi ; Kreutzer, Stephan; Mohar, Bojan (2010), "Inserciones planas y sin enlaces en 3 espacios y el problema de los nudos", Proc. Simposio ACM sobre geometría computacional (SoCG '10) , págs. 97–106, doi : 10.1145 / 1810959.1810975.
- Lovász, László ; Schrijver, Alexander (1998), "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de gráficos incrustables sin enlaces", Proceedings of the American Mathematical Society , 126 (5): 1275-1285, doi : 10.1090 / S0002-9939-98- 04244-0.
- Mader, W. (1968), "Homomorphiesätze für Graphen", Mathematische Annalen , 178 (2): 154–168, doi : 10.1007 / BF01350657.
- Motwani, Rajeev ; Raghunathan, Arvind; Saran, Hazur (1988), "Resultados constructivos de grafos menores: incrustaciones sin enlaces", Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS '88) , págs. 398–409, doi : 10.1109 / SFCS.1988.21956.
- Nešetřil, Jaroslav ; Thomas, Robin (1985), "Una nota sobre la representación espacial de gráficos" , Commentationes Mathematicae Universitatis Carolinae , 26 (4): 655–659, archivado desde el original el 18 de julio de 2011.
- Robertson, Neil ; Seymour, Paul (1995), "Graph Minors. XIII. El problema de los caminos disjuntos", Journal of Combinatorial Theory, Serie B , 63 (1): 65-110, doi : 10.1006 / jctb.1995.1006.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993a), "Un estudio de incrustaciones sin enlaces", en Robertson, Neil ; Seymour, Paul (eds.), Teoría de la estructura de grafos: Proc. Conferencia de investigación conjunta de verano AMS-IMS-SIAM sobre menores gráficos (PDF) , Matemáticas contemporáneas, 147 , American Mathematical Society, págs. 125-136.
- Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993b), "Incrustaciones sin enlaces de gráficos en 3 espacios", Boletín de la American Mathematical Society , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063.
- Robertson, Neil ; Seymour, PD ; Thomas, Robin (1995), "Conjetura de incrustación sin enlaces de Sachs", Journal of Combinatorial Theory, Serie B , 64 (2): 185-227, doi : 10.1006 / jctb.1995.1032.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993c), "Conjetura de Hadwiger para gráficos libres de K 6 " (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007 / BF01202354.
- Sachs, Horst (1983), "Sobre un análogo espacial del teorema de Kuratowski sobre grafos planos - un problema abierto", en Horowiecki, M .; Kennedy, JW; Sysło, MM (eds.), Graph Theory: Actas de una conferencia celebrada en Łagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, págs. 230–241, doi : 10.1007 / BFb0071633.
- Saran, Hazur (1989), Resultados constructivos en grafos menores: incrustaciones sin enlaces , Ph.D. tesis, Universidad de California, Berkeley.
- Truemper, Klaus (1992), Descomposición de matroides (PDF) , Academic Press, págs. 100–101.
Otras lecturas
- Ramírez Alfonsín, JL (2005), "Nudos y vínculos en grafos espaciales: una encuesta", Matemáticas discretas , 302 (1–3): 225–242, doi : 10.1016 / j.disc.2004.07.035.