algorithm - グラフのエッジ交差の削減

Question

グラフのエッジ交差を最小限に抑えるアルゴリズムはありますか? たとえば、グラフの遷移行列があるとします。

ノードを他のノードの周りに配置しようとする方法を見つけましたが、他のアイデアを知りたいです。

Answer 1

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

無向グラフを描画するための一般的な選択肢は、力ベースのレイアウト アルゴリズムです。このアルゴリズムでは、グラフのエッジはバネ (引力) として扱われ、頂点は荷電粒子 (反発力を適用) のように扱われます。アルゴリズムは、定常状態に達するまで、これらの力に基づいて頂点の位置を更新することによって機能します。力ベースの方法の詳細については、こちらをご覧ください。これらのアルゴリズムは平衡解を探すため、多くの場合、エッジのもつれがほとんどなく、疑似最適なレイアウトが得られます。

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