그래프에서 교차 가장자리를 최소화하십시오

Question

나는 Networkx (Python 그래프 그리기 패키지)를 사용하고 있습니다. http://networkx.lanl.gov/index.html.a> 내 프로젝트 중 하나.Networkx는 꽤 멋지 지 않지만 크로스 모서리의 수로 인해 Display 기능이 흡입됩니다.그래프에서 크로스 모서리를 최소화하는 방법이 있습니까?나는 크로스 에지가 최소화되도록 노드를 정렬 할 수있는 알고리즘을 의미합니까?

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.