Embebido sin enlaces

[5]​ Cuando un círculo se asigna a un espacio euclídeo 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.Si no existe tal movimiento continuo, se dice que las dos curvas están enlazadas.Por el contrario, si existe tal disco, las curvas están necesariamente desvinculadas.Con esta restricción, dos proyecciones cualesquiera conducen al mismo número de enlace.Cualquier grafo finito tiene un número finito (aunque puede ser exponencial) de ciclos simples distintos, y si el grafo está embebido en un espacio tridimensional, cada uno de estos ciclos forma una curva cerrada simple.Se dice que el embedido es plano si cada ciclo limita un disco de esta manera.Sin embargo, Sachs no pudo probar que estos fueran los únicos grafos vinculados mínimos, aunque Robertson, Seymour y Thomas (1995) finalmente logró demostrarlo.Su algoritmo encuentra grandes subgrafos planos dentro del grafo dado de tal manera que, si existe un embedido sin enlace, debe respetar el embedido plano del subgrafo.[12]​ También se pueden definir familias de grafos por la presencia o ausencia de nudos y enlaces más complejos en sus embebidos,[13]​ o por embebidos sin enlaces en variedades tridimensionales que no sean el espacio euclídeo.[14]​Flapan, Naimi y Pommersheim (2001) define un grafo embebido como triplemente enlazado si posee tres ciclos, ninguno de los cuales puede separarse de los otros dos; y demostraron que K9 no tiene un triple enlace intrínseco, pero K10 sí que lo tiene.[15]​ De manera más general, se puede definir un embedido n-enlazado para cualquier n como aquel que contiene un enlace de componente n que no puede dividirse mediante una esfera topológica en dos partes separadas.Estos problemas fueron finalmente resueltos por Robertson, Seymour y Thomas (1995),[18]​ quienes demostraron que los siete grafos de la familia de Petersen son los únicos menores mínimos prohibidos para estos grafos.El teorema del snark implica que cada grafo integrable sin enlaces cúbico es 3-aristas-coloreable.Algorítmicamente, el problema de reconocer grafos embebibles planos y sin enlaces se resolvió una vez que se demostró la caracterización del menor prohibido: se puede usar un algoritmo de Robertson y Seymour (1995) para probar en tiempo lineal si un grafo dado contiene alguno de los siete menores prohibidos.[19]​ Este método no construye incrustaciones planas o sin enlaces cuando existen, pero van der Holst (2009) desarrolló un algoritmo que construye un embedido, y Kawarabayashi, Kreutzer y Mohar (2010) encontró un algoritmo de tiempo lineal más eficiente.