Способы отображения ориентированного ациклического графа в сетку / матрицу

Question

У меня есть DAG со многими тысячами вершин и ребер.

Я ищу алгоритмы, которые могут позиционировать вершины в точках сетки таким образом, чтобы это было наиболее дружественным для человека / эстетическим.Я догадываюсь, что самый лучший макет будет похож на макет с минимальной суммой длин ребер.

Можете ли вы указать мне эффективные алгоритмы для такой минимальной суммы макетов длин ребер, или другие алгоритмы, которые могут мне помочьрешить эту проблему?

Вот часть результатов очень наивного алгоритма:

Answer 1

Я почти уверен, что это открытая проблема (" графика "). Пара других вещей, которые вы могли бы рассмотреть возможность оптимизации:

• Угол между ребрами, идущими от вершины (максимизировать)
• Количество пересечений краев (свести к минимуму)

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