El problema de las dos trayectorias

Dada una gráfica G y cuatro vértices especiales x, y, x', y'; el problema de las dos trayectorias consiste en decidir si en G hay dos trayectorias disjuntas que unan los pares (x, y), (x', y'). Inesperadamente, la solución a este problema tiene un sabor topológico: Decidir si una gráfica tiene o no dichos dos caminos es equivalente a decidir si la gráfica tiene un dibujo particular en el plano. Tomaremos esto de pretexto para introducir el problema del número de cruces, que básicamente es, encontrar para cada gráfica un dibujo en el plano con el menor número de cruces entre pares de aristas. El problema del número de cruces ha mostrado ser resistente al paso del tiempo; no obstante, recientemente se han dado resultados estructurales muy importantes. Uno de ellos es la clasificación de casi todas las gráficas 2-cruce-críticas de Bokal, B. Oporowski, R. B. Richter y G. Salazar. En un intento por terminar la clasificación, una caracterización de las gráficas que no tienen dos xy-, x'y'-trayectorias disjuntas sirvió como herramienta para cerrar más esta brecha. Siguiendo la dinámica preguntona, nos centraremos en explicar esta caracterización que es un puente entre un problema combinatórico y uno topológico.