Layouts de gráficos planares

Question

Quais são algumas técnicas de minimização de sobreposição de arestas ao traçar um gráfico?(De preferência relacionado ao GraphViz) Também existe algum software que possa fazer o layout de um gráfico de forma planar?

Layout Atual - http://www.evecakes.com/doodles/master.gif

A seção rosa no canto superior esquerdo parece boa, enquanto a seção azul claro tem algumas sobreposições de borda evitáveis.

Answer 1

Para gráficos gerais, o problema de determinar um layout plano de um gráfico com menos arestas cruzadas (o Número de cruzamento) é NP-difícil.Portanto, alguns métodos heurísticos são usados ​​(como o Layout baseado em força algoritmos).

A página abaixo descreve brevemente os algoritmos graphviz e sugere algumas maneiras de usá-los para obter benefícios.Também contém links para os pdfs que devem conter mais informações sobre os algoritmos:

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

Espero que ajude.

Answer 2

A seguinte biblioteca Java de código aberto possui alguns algoritmos que podem ajudar no layout de gráficos planares.http://open.trickl.com/trickl-graph/index.html

Em particular, as seguintes classes fornecem soluções analíticas para o problema:

ChrobakPayneLayout (baseado na implementação Boost C++ de Aaron Windsor)http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout (Com base na localização distribuída sem âncora em redes de sensores * Nissanka B.Priyantha, Hari Balakrishnan, Erik Demaine e Seth Teller)

O que você pode querer fazer é usar algo assim como a primeira "tentativa", o que garante que não haja sobreposições, embora possa não parecer ótimo.Então você pode aplicar um algoritmo direcionado à força para espaçar os nós de maneira mais justa.

Infelizmente, a biblioteca acabou de ser lançada, por isso falta documentação.No entanto, pode ser útil fornecendo algum código real em vez de apenas teoria.