graph-theory - 平面グラフ描画アルゴリズム

Question

彼の顔のリストがある場合、平面グラフを描画するアルゴリズムはありますか?

パスの追加や頂点の追加など、平面性をテストして平面埋め込みを生成する複雑なアルゴリズムがいくつかあることは知っていますが、それは私が探しているものではありません。

Answer 1

グラフを視覚化するためのテクニックは数多くあり、教科書全体がそのテーマに専念しています。実装する簡単なアルゴリズムを探している場合は、力指向グラフの描画を参照することをお勧めします。

アイデアは、頂点が自然に互いに反発することを考慮しますが、エッジはそれらを一緒に描画することです。両方の力 (反発力と引力) は、頂点間の距離の関数であり、関連する頂点に向かって (または頂点から離れて) 直接作用する必要があります。斥力は (1/r^2)、引力は ln(r) のような大きさが適しています。また、境界に適用されるいくつかの反発力を考慮して、個別の接続されたコンポーネントが無限に飛び散るのを防ぎます。

そのアルゴリズムは次のようになります。

1. すべての頂点を平面上のランダムな点に配置します。

2. 各頂点に作用する正味の力を計算します。

3. 正味の力の分数で各頂点を移動します。

4. ある許容値を超えて移動した頂点がない場合は、グラフを描画し、そうでない場合は 2 に進みます。

アニメーションが必要な場合は、ステップ 4 を「グラフを描画してから 2 に進む」に置き換えることができます。

高速ではなく、平面表現を保証するものではありませんが、実装は簡単で、一般に平面性をうまく捉えることができます。高度に接続された頂点は、互いに近くなります。