¿Existe un algoritmo adecuado para dibujar un gráfico mixto de circunscripción / dependencia en un sistema de coordenadas?

Estoy buscando un algoritmo para dibujar un gráfico mixto de circunscripción / dependencia (para una aplicación lingüística). Tal gráfico tendría dos tipos diferentes de vértices (tokens, nodos) y dos tipos diferentes de bordes (jerárquico, no jerárquico).

Soy nuevo en teoría de gráficos y algoritmos en general, y espero que esta pregunta no choque, por ejemplo, con los requisitos de nivel de investigación de este sitio. Sin embargo, generalmente debe estar dentro del alcance de la teoría .

El gráfico debería dibujarse de abajo hacia arriba (creo), ya que todos los tokens deberían mostrarse con la misma coordenada y, y las coordenadas y de los nodos que agrupan tokens y / o nodos en constituyentes deberán calcularse dinámicamente, por ejemplo, a través de su camino más largo a un token.

Los bordes jerárquicos (utilizados para agrupar tokens / nodos en constituyentes) deben tener un número mínimo de puntos de inflexión (idealmente 0), pero también debe haber un número mínimo de cruces, sobrescribiendo el requisito anterior si es necesario.

Las aristas no jerárquicas (utilizadas para dependencias) deben tener un número mínimo de cruces y dibujarse como curvas de Bézier.

La siguiente mejor cosa que he encontrado es el algoritmo descrito por Buchheim et al. , mejorando el algoritmo de Walker para ejecutarse en tiempo lineal.

Por favor, hágamelo saber si es necesario mejorar mi pregunta, y muchas gracias de antemano por cualquier sugerencia.

EDITAR:

Como se señaló en un comentario, debo mencionar que básicamente quiero un diseño de gráfico predeterminado por un algoritmo, que yo, a la larga, quiero editar y revisar dentro de las posibilidades de Eclipse GEF . Anteriormente he buscado opciones para hacer que Graphviz funcione con GEF, pero parece que no hay una solución de trabajo que conserve toda la funcionalidad de edición heredada de GEF.

parece que quieres lo siguiente

• Un algoritmo de diseño gráfico. muchos algoritmos estándar normalmente usan métodos basados ​​en la fuerza donde los nodos están conectados por "resortes" repulsivos / atractivos y el estado de equilibrio / baja energía se obtiene a través de una cierta cantidad de iteración (de la ecuación diferencial relacionada con la fuerza construida globalmente). la salida del algoritmo es un conjunto de coordenadas 2-d o 3-d para nodos y (generalmente) aristas.
• capacidad de modificar a mano los resultados de ese algoritmo. típicamente llamado un "editor de gráficos". Esto comienza con las coordenadas del algoritmo de diseño y permite el ajuste.

re (1) el software de vanguardia parece ser graphviz . re (2) vea, por ejemplo, esta pregunta "cuál es el mejor editor de gráficos" en mathoverflow .

navegando por la galería de graphviz, aquí hay dos tipos de gráficos similares a los que desea.

Diagrama ER y semáforo .

Dices que tienes dos tipos de bordes. una manera simple sería tener bordes dirigidos "hacia o lejos" como en el ejemplo del semáforo. o los bordes se pueden etiquetar de dos maneras como en el diagrama ER. ambos ejemplos muestran dos tipos de nodos diferentes usando diferentes formas o etiquetas, o sombreado, etc. otros enfoques serían usar colores.

como las preguntas y respuestas de mathoverflow indican que hay muchos editores de gráficos. el estándar con graphviz es "dotty". ver, por ejemplo, pdf "edición de gráficos con dotty" por Koutsofious.

Otra técnica para graficar, posiblemente gráficos grandes, es observar composiciones estructurales, por ejemplo, descomposiciones de camarillas.