平面埋め込みを認証する方法

Question

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

私は一連のグラフ（href="http://www.graphdrawing.org/data/" real="noreferrer">ローマグラフ）を実行することで、結果を検証し始めました。私の結果を別の実装の結果（YFiles）と比較します。ただし、所定の平面グラフでは、さまざまな埋め込みが存在する可能性があるため、平面/非面の回答が等しいかどうかを確認できます。

計算した埋め込み（隣接リスト内の順序付け）が正しい平面埋め込みであることを確認する方法はありますか？

私はすでに私がおそらく間違った埋め込みを受ける場合に発見されました。グラフに障害が発生するためには、通常埋め込みを手動で描画します。 docs 状態であることがわかりました。任意のグラフであれば、グラフの平面図面を作成することができ、グラフが平面であり、平坦性の証明書が確認が容易であることを証明できます。しかし、私がそのような絵を絶対に並んだアルゴリズムの順序で創造する方法で、そして私がそのような図面を作成することができるかどうかはわからない。

（ここに私のhref="https://github.com/bxt/smoth/blob/master/src/de/uniwue/smooth/planar/brandesembedding.java" rel="noreferrer">コード）

Answer 1

私が知っている最も簡単な方法は、任意のスパニングツリーを計算することです。次に、残りのエッジにデュアルグラフにサイクルがないことを確認します。DNEXT（e）がヘッドVで反時計回りの次のハーフエッジにHEAR-EDESをハーフエッジEにマッピングすると、SYM（E）はEと反対の半辺になり、次にRPREV（E）= SYM（DNEXT）です。（e））同じ右面で時計回りに次の半縁です。私はアルゴリズムでこのアプローチを実装しました。 http://www.davideisenstat.com/トリクル/

あるいは、Euler特性を使用することができます。ラベル（=置換DNextのサイクル）と面（=置換RPREVのサイクル）を参照して、接続されているコンポーネントの数を決定します。（V-C）+（F - C）= e。