Diseños de gráfico planar

¿Cuáles son algunas técnicas de minimización de superposición de bordes al diseñar un gráfico? (Preferiblemente relacionado con GraphViz). ¿Existe algún software existente que pueda diseñar un gráfico de manera plana?

Diseño actual – http://sofes.miximages.com/algorithm/master.gif

La sección rosa en la esquina superior izquierda se ve bien, mientras que la sección azul claro tiene algunas superposiciones de borde evitables.

Para gráficos generales, el problema de determinar un diseño plano de un gráfico con un cruce de bordes mínimo (el Número de cruce ) es NP-hard. Entonces se usan algunos métodos heurísticos (como los algoritmos de diseño basados ​​en la Fuerza ).

La siguiente página describe brevemente los algoritmos graphviz y sugiere algunas formas de usarlos para beneficio. También tiene enlaces a los pdfs que deberían contener más información sobre los algoritmos:

http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

Espero que ayude.

La siguiente biblioteca Java de código abierto tiene un par de algoritmos que pueden ayudar a diseñar gráficos planos. http://open.trickl.com/trickl-graph/index.html

En particular, las siguientes clases proporcionan soluciones analíticas para el problema:

ChrobakPayneLayout (basado en la implementación de Boost C ++ por Aaron Windsor) http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout (basado en la localización distribuida libre de anclaje en redes de sensores * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine y Seth Teller)

Lo que podría querer hacer es usar algo como esto como el primer “bash” que asegura que no haya superposiciones, aunque puede que no se vea muy bien. Luego puede aplicar un algoritmo dirigido por la fuerza para espaciar los nodos de manera más justa.

Lamentablemente, la biblioteca acaba de ser lanzada, por lo que no cuenta con documentación. Sin embargo, podría ser útil al proporcionar algún código real en lugar de simplemente la teoría.