¿Cómo reducir el número de bordes cruzados en un diagrama?

Estoy trabajando en un editor de diagramas. Los diagramas muestran formas 2D ( nodos ) conectadas con conectores ( bordes ).

Me gustaría agregar una operación que, dada una selección de nodos, los "desenrede" : los reposiciona para reducir el número de bordes cruzados, si es posible (y está bien si los bordes tendrán que dibujarse con puntos de curvatura) .

Entonces, quiero un algoritmo gráfico que, dada una incrustación gráfica ( topológica ) y un subconjunto de sus nodos, modifique la incrustación (su topología ) solo en esos nodos para minimizar el número de bordes cruzados.

Al leer sobre gráficos de ápice y navegar por Cabello y Mohar (2013) , supongo que este problema es NP-hard. Por lo tanto, estaré contento con un algoritmo parametrizado (por ejemplo, en el número de bordes cruzados) que tiene una complejidad de tiempo conocida, polinómica, para cualquier valor de parámetro dado. Esto parece factible, pero no me resulta fácil crear un algoritmo por mi cuenta.

Preguntas:

• ¿Dónde busco tal algoritmo?
• ¿Existe?
• En el software existente?
• ¿Existe alguna experiencia práctica significativa con tal operación? (Lo que se ve bien en teoría puede no ser tan bueno en la práctica, o viceversa).

(No estoy seguro de dónde hacer esta pregunta: ¿aquí, en StackOverflow o MathOverflow?)

$\text{NP-hard}$

El problema planteado en la pregunta es en realidad más difícil y más complicado que el anterior. Está considerando nodos gráficos de cierto tamaño y forma, al tiempo que limita el tamaño (área) del resultado. Además, se desea una noción de estética aún no determinada. Obviamente, queremos una heurística para esto, que no utiliza el mínimo absoluto en el caso general. El número de nodos encontrados en una aplicación de este tipo probablemente no sea enorme en el caso promedio. Dibujar la versión mínima de cruce de bordes del gráfico puede ser factible para tamaños pequeños.

Recursos:
Puede estar interesado en los siguientes recursos, particularmente con los primeros:

• La documentación para una característica del paquete Graphviz presenta un algoritmo que genera gráficos dirigidos de aspecto agradable: http://www.graphviz.org/Documentation/TSE93.pdf
  Tiene muchas otras características que pueden resultar útiles. El código fuente se encuentra en su sitio web bajo EPL. También incluye una página dedicada a la teoría detrás de la visualización gráfica.
• Para un algoritmo de parámetros fijos, consulte un documento de Martin Grohe:
  Cálculo de números cruzados en tiempo cuadrático
• Una charla técnica dada por Amina Shabbeer en RPI:
  preservando las relaciones de proximidad y minimizando los cruces de bordes en las incrustaciones de gráficos
• Julia Chuzhoy puede encontrar un ejemplo de un algoritmo probabilístico eficiente :
  un algoritmo para el problema del número de cruce de gráficos

También hay muchos otros recursos. Esto debería ayudarlo a comenzar.

Pensamientos y observaciones adicionales:

Aquí hay una idea para evitar los problemas relacionados con la forma y el tamaño de los nodos. Dado el gráfico (nodos infinitamente pequeños), expanda cada nodo mientras "empuja" o dobla los bordes (por ejemplo, usando splines mientras impone un límite de proximidad). Debe hacer esto con otros bordes y nodos que se interpongan en su camino, lo que puede iniciar una reacción en cadena. Analice cómo se pueden calcular eficientemente los equilibrios (por ejemplo, estructuras moleculares). Si no puede obtener la forma de un nodo al tamaño deseado, entonces escale todo el diagrama.

Un usuario puede disfrutar de los resultados de un algoritmo aleatorio. Podrían usar su función varias veces hasta que obtuvieran algo que les gustara. Evite el cálculo redundante en este caso (no es necesario volver a calcular un número cruzado).