有向非循環グラフをグリッド/マトリックスにマッピングする方法

Question

私は数千の頂点とエッジを持つDAGを持っています。

グリッドポイント上に頂点を配置できるアルゴリズムを探していますが、それは最も人間的なやり方です。私の感心しているのは、最もすばらしいレイアウトは、最小のエッジ長の合計を持つレイアウトに似ているということです。

このようなエッジの長さのレイアウトの最小合計、またはこの問題に取り組むのに役立つ他のアルゴリズムの効率的なアルゴリズムを教えてください。

はここで非常にナイーブなアルゴリズムからの出力の一部です：

Answer 1

私は、これは未解決の問題であるかなり確信している（「graph drawing」）。 （最大化）エッジ交差の

数の頂点からエッジ間

• 角度

あなたが使用することができるかもしれません（最小化）：カップル他のものは、あなたが最適化を検討する必要があります遺伝的アルゴリズムやその他の種類のmetaheuristicでも、結果はどれくらい良いか分かりません。