グラフの辺の交差を減らす

Question

グラフの辺の交差を最小限に抑えるアルゴリズムがあるかどうかを尋ねたいと思います。

他のノードの周りにノードを配置しようとするようなメソッドが見つかりましたが、私はいくつかの他のアイデアを知りたいと思います。ありがとう。

Answer 1

グラフ描画アプリケーションのために開発された幅広い確立されたアルゴリズム/ライブラリがあります。少し背景を得ることができますhere

無向グラフを描画するには、グラフエッジをバネ（引力）として扱い、頂点を荷電粒子のように扱う（反発力を適用する）力ベースのレイアウトアルゴリズムが一般的です。このアルゴリズムは、定常状態に達するまで、これらの力に基づいて頂点位置を更新することによって機能する。あなたは力ベースの方法についての詳細を読むことができますhere。これらのアルゴリズムは平衡解を探索するため、しばしば絡み合うことなく、擬似最適レイアウトになります。

利用可能な多くのグラフ描画ライブラリの1つを使用したいと思うかもしれません。 Graphvizパッケージは、一般的にはかなり優れており、さまざまなグラフ描画アプリケーションにさまざまなアルゴリズムをサポートしています。