graph - 平面グラフ（幾何学的形状）の境界（境界）エッジを検索します

Question

平面の幾何学的形状を表す頂点とエッジリストがあります（面は三角形です）。例えば：

   a_______b
   /|\    /
  / | \  /
e/__|__\/c
    d

Verts: a, b, c, d, e
Edges: (a,b), (a,c), (a,d), (a,e), (b,c), (c,d), (d,e)

これが、その特定の平面幾何学的形状について私が持っているすべての情報です。この例では、内部エッジは（a、c）と（a、d）のみです。他のすべてのエッジは境界エッジです。これらの境界エッジをアルゴリズムで識別する（または逆にすべての内部エッジを識別する）にはどうすればよいですか？

動機：それが役立つ場合、私はナビゲーションメッシュを構築しようとしています。そのステップの1つは、可視性グラフを構築することです。その最初のステップは、境界エッジを識別することだと思います。

Answer 1

平面グラフの場合、「外面」プロパティは一意ではありません。いずれかの面が外側になるようにグラフを描画することも、異なる面を持つようにグラフを描画することもできます。グラフの例を考えてみましょう。

とはいえ、すべての内面が三角形になるようにグラフを描画できることがわかっている場合は、エッジのリストをスキャンして、それらが属する三角形の数を確認できます（隣接するエッジを確認することにより）。エッジが1つの三角形のみに属する場合、それは外側のエッジです。

とにかく、グラフがそのような特性を持っていることを知っていて、同時にそれぞれの平面埋め込みが何であったかを知らないのは、私には奇妙に思えます。

Answer 2

私は少し遅れていることを知っています。FEMコミュニティでは、各三角形のエッジをカウントし、境界は1回表示されるエッジです。それがスパース行列で行われる場合、それは（私にとって）かなり高速です。