最小交点レイアウトアルゴリズム

Question

グラフの最小交点レイアウトアルゴリズム（力点ではない）の例があるかどうかを知りたいので、それをd3.jsに適合させることができます。

Answer 1

エッジ交差を最小限に抑えるグラフのレイアウトを計算するのはNP困難なので、アルゴリズムは1つではありません。異なるトレードオフの異なるアルゴリズムがあります。力ベースのレイアウト（Fruchterman–Reingold）は1つのアプローチであり、レイヤード（Sugiyama）が別のアプローチです。ツリー（Reingold–Tilford）や小さな世界（van Ham–van Wijk）など、特定の種類のグラフのレイアウトもあります。 Dig-CoLa（Dwyer–Koren）のような制約のあるレイアウトは、アルゴリズムのさらに別のクラスです。

エッジクロッシングの数を最小限に抑えるアルゴリズムを具体的に使用する場合は、simulated annealingを使用できます。これは最終的に正しい答えを見つけることができますが、それはかなり遅くなる可能性があります。