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

Question

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

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

11

algorithm graph networkx planar-graph

Источник

user516730 20 фев '11 в 16:10

1 ответ

Решение

Другие вопросы по тегам algorithm graph networkx planar-graph

20 фев '11 в 16:16 2011-02-20 16:16 · Accepted Answer · 2011-02-20 16:16

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

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

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

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