平面グラフの境界（境界）エッジを見つける（幾何学的形状）

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になるように、あなたは、グラフを描くことができ、またはあなたも、それは別の顔を持っていることを、このようなグラフを描くことができます - あなたの例のグラフを考えてみます。

あなたならば、言ったことすべての内部面が三角形であるようにグラフを描くことができることを知っていれば、辺のリストをスキャンして、それらが属している三角形の数をチェックすることができます。エッジが1つの三角形にのみ属する場合、それは外側のエッジです。

とにかく、グラフがそのような特性を持ち、それぞれの平面埋め込みが同じ瞬間にあったかどうかわからないことは、私にとっては奇妙なことです。