7

平面埋め込みを計算するアルゴリズムを実装しようとしています。

一連のグラフ ( rome graphs ) に対して実行し、結果を別の実装 (yfiles) の結果と比較することで、結果の検証を開始しました。ただし、特定の平面グラフにはさまざまな埋め込みが存在する可能性があるため、平面/非平面の答えが等しいかどうかのみを確認できます。

計算した埋め込み (隣接リストでの順序付け) が正しい平面埋め込みであることを確認するにはどうすればよいですか?

おそらく間違った埋め込みを取得するいくつかのケースをすでに発見しました。失敗したグラフの場合、通常、埋め込みを手動で描画するのは困難です。任意のグラフを指定すると、グラフの平面図を作成できるというブースト ドキュメントの状態がわかりました。これにより、グラフが平面であり、平面性の証明書が簡単に確認できることが証明されます。しかし、順序付けられた隣接リストだけから、絶対確実なアルゴリズムの方法でそのような図面を作成できるかどうか、またはどのように作成できるかもわかりません。

（ところで、ここに私のコードがあります）

4

1 に答える 1

3

私が知っている最も簡単な方法は、任意のスパニング ツリーを計算してから、双対グラフで残りのエッジにサイクルがないことを確認することです。dnext(e) がヘッド v を持つハーフエッジ e を、ヘッド v を持つ反時計回りの順序で次のハーフエッジにマッピングし、sym(e) が e の反対側のハーフエッジである場合、rprev(e) = sym(dnext (e)) は、同じ右面を持つ時計回りの次のハーフエッジです。私は私のプロジェクトの Algorithm.java でこのアプローチを実装しました: http://www.davideisenstat.com/trickle/

あるいは、オイラー標数を使用することもできます。頂点 (= 順列 dnext のサイクル) と面 (= 順列 rprev のサイクル) にラベルを付け、いくつの連結成分が存在するかを決定します。(V - C) + (F - C) = E であることを確認します。

于 2014-02-25T14:37:37.197 に答える