平面グラフでの小サイクル発見

Question

幾何学的な無向平面グラフ、つまり各ノードに場所があるグラフ2つのエッジが交差していないので、エッジが交差していないすべてのサイクルを見つけたい。

この問題の良い解決策はありますか？

---

私がやろうとしているのは、 A * のようなソリューションです。

• 最小ヒープ内のすべてのエッジをパスとして挿入
• すべてのオプションで最短パスを延長する
• 開始以外の場所にループバックするカルパス（必要ない場合があります）
• angで指定されたエッジを使用する3番目のパスを選択する

これに関する問題は誰にも見られますか？動作しますか？

Answer 1

私の最初の本能は、ウォールフォロー迷路ソルバーに似た方法を使用することです。基本的に、エッジをたどり、常に頂点から右端のエッジを取り出します。この方法で発生するサイクルはすべて、顔の境界になります。どのエッジをどの方向に移動したかを追跡する必要があります。エッジを両方向にトラバースすると、それが分離する面を識別しました。すべてのエッジが両方向にトラバースされると、すべての面を境界で識別できます。

Answer 2

「クロスエッジ」とは、一般にコードとして知られています。 。したがって、問題はすべてのコードレスサイクルを見つけることです。

このペーパーは役立つようです。

Answer 3

これを行う簡単な方法は、外に出て各面を列挙することです。原理は簡単です：

• 各エッジの「＆＃945; -visited」および「＆＃946; -visited」フラグと、各フラグの未訪問エッジの二重リンクリストを管理します。 「＆＃945;」および「＆＃946;」分割は、問題のエッジに対応するライン上の平面のパーティションに対応する必要があります。どちら側が＆＃945;そしてどちら側が＆＃946;任意です。
• 各頂点Vについて：
  • エッジの各隣接ペアE =（V_1、V）、E '=（V_2、V）（つまり、角度で並べ替え、隣接するペアを取得し、first + last）：
  • VがEのどちら側S（S =＆＃945;または＆＃946;）にあるかを判断します。
  • 以下に説明するように、EのサイドSを使用してVからタイルを歩いてください：

タイルの歩行は次の方法で実行されます：

• V = V_init
とする
• ループ：
  • V_next = VではないEの頂点
  • E '= Eの現在の側にあるV_nextからEに隣接するエッジ
  • S '= Vを含むE'の側
  • V_next = Vの場合、ループが見つかりました。途中で通過したすべてのエッジを記録し、それらのエッジペアを訪問済みとしてマークします。
  • E '= E（エッジが1つしかない）の場合、行き止まりになっています。この散歩を中止
  • それ以外の場合、V = V_next、E = E '、S = S'とし、続行します。

これが理にかなったことを望みます。おそらく説明するためにいくつかの図が必要です...