Existe um algoritmo adequado para desenhar um gráfico misto de constituição / dependência em um sistema de coordenadas?

Estou procurando um algoritmo para desenhar um gráfico misto de constituição / dependência (para um aplicativo linguístico). Esse gráfico teria dois tipos diferentes de vértices (tokens, nós) e dois tipos diferentes de arestas (hierárquica, não hierárquica).

Eu sou novo na teoria dos grafos e algoritmos em geral, e espero que essa pergunta não colide, por exemplo, com os requisitos de nível de pesquisa deste site. No entanto, geralmente deve estar no escopo da história .

O gráfico teria que ser desenhado de baixo para cima (eu acho), pois todos os tokens devem ser exibidos com a mesma coordenada y, e as coordenadas y dos nós que agrupam tokens e / ou nós em constituintes terão que ser calculadas dinamicamente, por exemplo, pelo caminho mais longo para um token.

As arestas hierárquicas (usadas para agrupar tokens / nós em constituintes) devem ter um número mínimo de pontos de curvatura (idealmente 0), mas também deve haver um número mínimo de cruzamentos, substituindo o requisito anterior, se necessário.

As arestas não hierárquicas (usadas para dependências) devem ter um número mínimo de cruzamentos e ser desenhadas como curvas de Bézier.

A próxima melhor coisa que me deparei é o algoritmo descrito por Buchheim et al. , melhorando o algoritmo de Walker para executar em tempo linear.

Informe-me se houver necessidade de melhorar minha pergunta e desde já agradeço muito por qualquer indicação.

EDITAR:

Como apontado em um comentário, devo mencionar que basicamente quero um layout de gráfico padrão por um algoritmo que, a longo prazo, eu quero editar e revisar dentro das possibilidades do Eclipse GEF . Anteriormente, examinei as opções para que o Graphviz funcionasse com o GEF, mas parece não haver uma solução funcional que preserve todas as funcionalidades de edição herdadas do GEF.

você parece querer o seguinte

• um algoritmo de layout de gráfico. muitos algoritmos std normalmente usam métodos baseados em força, em que os nós são conectados por "molas" atraentes / reutilizáveis ​​e o estado de equilíbrio / baixo consumo de energia é obtido por meio de uma grande quantidade de iterações (da correspondente equação diferencial relacionada à força globalmente construída). a saída do algoritmo é um conjunto de coordenadas 2-d ou 3-d para nós e (geralmente) arestas.
• capacidade de modificar manualmente os resultados desse algoritmo. normalmente chamado de "editor de gráficos". isso começa com as coordenadas do algoritmo de layout e permite o ajuste.

re (1) o software de primeira linha parece ser graphviz . re (2) veja, por exemplo, esta pergunta "qual é o melhor editor de gráfico" no mathoverflow .

navegando na galeria graphviz, aqui estão dois tipos de gráficos semelhantes ao que você deseja.

Diagrama de ER e semáforo .

você diz que tem dois tipos de arestas. uma maneira simples seria ter as bordas direcionadas "na direção ou fora", como no exemplo do semáforo. ou as bordas podem ser rotuladas de duas maneiras, como no diagrama de ER. os dois exemplos mostram dois tipos diferentes de nós usando formas ou rótulos diferentes, sombreamento, etc. outras abordagens seriam usar cores.

como o Q / As do mathoverflow indica que existem muitos editores de gráfico. o padrão com graphviz é "dotty". veja por exemplo pdf "editando gráficos com dotty" por Koutsofious.

Outra técnica para representar graficamente, possivelmente grandes gráficos, é examinar composições estruturais, por exemplo, decomposições de cliques.