Минимизируйте перекрестные края на графике

Question

Я использую networkx (пакет для рисования графов Python) http://networkx.lanl.gov/index.html для одного из моих проектов.Хотя networkx довольно крутой, функция отображения отстой из-за количества поперечных граней.Есть ли способ минимизировать поперечные ребра на графике?Я имею в виду алгоритм, который может сортировать узлы таким образом, чтобы поперечные ребра были минимизированы?

Answer 1

Определение планарного графика, который минимизирует количество пересечений, является NP-Hard.См. Вики-страницу на Пересеченное число .

Вы можете попробовать некоторые эвристики, я полагаю, что макет на основе силы довольно популярен (графвиз использует их, если я правильно помню).

Вы также можете попробовать некоторые алгоритмы аппроксимации, вы должны найти ссылки на вики-странице, на которую я ссылаюсь.

Надеюсь, это поможет.