algorithm - 有向非巡回グラフをグリッド/マトリックスにマッピングする方法

Question

何千もの頂点とエッジを持つDAGがあります。

私は、最も人間に優しい/美的方法で頂点をグリッドポイントに配置できるアルゴリズムを探しています。私の勘では、最も優れたレイアウトは、エッジの長さの合計が最小のレイアウトに似ていると思います。

このようなエッジ長の最小合計レイアウトの効率的なアルゴリズム、またはこの問題に取り組むのに役立つ可能性のある他のアルゴリズムを教えていただけますか？

非常に単純なアルゴリズムからの出力の一部を次に示します。

Answer 1

これは未解決の問題であると確信しています（「グラフ描画」）。最適化を検討したい他のいくつかのこと：

• 頂点から来るエッジ間の角度（最大化）
• エッジ交差の数（最小化）

遺伝的アルゴリズムや他の種類のメタヒューリスティックを使用できるかもしれませんが、結果がどれほど良いかはわかりません。