javascript - 最小交差レイアウト アルゴリズム

Question

グラフの最小交差レイアウト アルゴリズム (強制ベースではない) の例があるかどうかを知りたいので、d3.js に適応させることができます。

Answer 1

エッジの交差を最小化するグラフのレイアウトを計算することは NP 困難であるため、単一のアルゴリズムはありません。さまざまなトレードオフを持つさまざまなアルゴリズムがあります。力ベースのレイアウト ( Fruchterman–Reingold ) は 1 つのアプローチであり、レイヤード (杉山) は別のアプローチです。木 ( Reingold–Tilford ) や小さな世界 ( van Ham–van Wijk )など、特定の種類のグラフのレイアウトもあります。Dig-CoLa ( Dwyer–Koren )などの制約付きレイアウトは、さらに別のクラスのアルゴリズムです。

エッジ クロッシングの数を最小限に抑えることを明確に求めるアルゴリズムが必要な場合は、シミュレーテッド アニーリングを使用できます。これは最終的に正しい答えを見つけますが、かなり遅くなる可能性があります。