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

10

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?)

reinierpost
fuente
1
Supongo que la pregunta puede ser más adecuada para StackOverflow, pero sí noté que preguntas similares allí tienen respuestas insatisfactorias. Seguiré con una respuesta que debería ayudarte en el aspecto teórico, pero puede ser mejor que tu pregunta sea migrada allí.
mdxn
Aquí se está haciendo un trabajo muy profundo: complang.tuwien.ac.at/cd/ebner/ebner05da.pdf
Dschoni
¡Gracias! No solo eso, sino que es claramente una presentación muy legible del problema y una encuesta de algunos enfoques bien conocidos.
reinierpost

Respuestas:

9

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:

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).

mdxn
fuente
Agregué topología a mi pregunta específicamente para evitar la discusión de la estética. Es importante, pero no creo que afecten demasiado el problema básico: creo que pueden tratarse en un paso separado, después de ajustar la topología de los nodos (es decir, qué nodos están rodeados por qué otros nodos).
reinierpost
La primera vez que utilicé Graphviz fue hace 15 años; Lo uso aproximadamente una vez por semana para todo tipo de gráficos. No estoy demasiado impresionado por sus resultados, y entiendo que es difícil hacerlo mucho mejor.
reinierpost
A menudo visito graphviz.org y he leído algunos de los documentos a los que se refieren. Pero todavía no he encontrado una respuesta a esta pregunta específica, y no está en la descripción de mi trabajo familiarizarme con la literatura. Por eso lo pregunto aquí.
reinierpost
Sin embargo, gracias por las referencias. Noté que esto todavía es una investigación actual .
reinierpost
Lo primero que intentaré es un algoritmo trivial (y por lo tanto no necesariamente útil) basado aproximadamente en la idea de la Sra. Shabbeer. Gracias de nuevo.
reinierpost