Sposoby mapowania skierowanego wykresu acyklicznego do siatki/macierzy

Question

Mam DAG z wieloma tysiącami wierzchołków i krawędzi.

Szukam algorytmów, które mogą pozycjonować wierzchołki na punktach siatki w sposób najbardziej przyjazny dla człowieka/estetyczny. Mam przeczucie, że najładniejszy układ będzie podobny do układu z minimalną sumą długości krawędzi.

Czy możesz wskazać mi wydajne algorytmy dla takiej minimalnej sumy układów długości krawędzi lub innych algorytmów, które mogłyby mi pomóc rozwiązać ten problem?

Oto część wyjściu z algorytmem bardzo naiwnych:

Answer 1

Jestem całkiem pewien, że to jest problemem otwartym („graph drawing”). Kilka innych rzeczy, może warto rozważyć optymalizację:

• Kąt między krawędziami pochodzących z wierzchołka (maksymalizacji)
• liczba przejść krawędź (zminimalizować)

może być w stanie używać algorytm genetyczny lub jakiś inny rodzaj metaheuristic, ale nie wiem, jak dobre będą wyniki.