Modi per mappare un grafo aciclico diretto su una griglia/matrice

Question

Ho un DAG con molte migliaia di vertici e spigoli.

Sto cercando algoritmi in grado di posizionare i vertici sui punti della griglia in un modo che sia il più umano/estetico. La mia impressione è che il layout più bello sarebbe simile al layout con la somma minima delle lunghezze dei bordi.

Potete indicarmi algoritmi efficienti per tale somma minima di layout di lunghezza dei bordi o altri algoritmi che potrebbero aiutarmi a risolvere questo problema?

Ecco parte della produzione da un algoritmo molto ingenuo:

Answer 1

Sono abbastanza sicuro che questo è un problema aperto ("graph drawing"). Un paio di altre cose che si potrebbero prendere in considerazione l'ottimizzazione:

• angolo tra i bordi provenienti da un vertice (massimizzare)
• Numero di incroci tra archi (minimizzare)

si potrebbe essere in grado di utilizzare un algoritmo genetico o qualche altro tipo di metaheuristic, ma non so quanto saranno buoni i risultati.