Minimizar as bordas cruzadas em um gráfico

Question

Eu estou usando o NetworkX (um pacote de desenho de gráfico Python) http://networkx.lanl.gov/index.html Para um dos meus projetos.Embora o NetworkX seja bem legal, o tipo de função de exibição é devido ao número de bordas cruzadas.Existe uma maneira de minimizar as bordas cruzadas em um gráfico?Quero dizer um algoritmo que pode classificar os nós de uma forma que as bordas cruzadas são minimizadas?

Answer 1

Determining a planar graph layout which minimizes the number of crossings is NP-Hard. See the wiki page on Crossing Number.

You could try some heuristics, force based layout are quite popular I believe (graphviz uses them, if I recollect correctly).

You could also try some approximation algorithms, you should find references on the wiki page I linked.

Hope that helps.