그래프의 바깥 쪽 가장자리 찾기

Question

그래프의 바깥 쪽 가장자리를 찾는 가장 좋은 방법은 무엇입니까? 예를 들어

,이 그래프의 빨간색 가장자리 :이 algortithm에 이름이있는 경우

는 모르겠어요. 그 이름은 Google에서 뭔가를 찾는데 도움이 될 것입니다.

Answer 1

나는이 질문에 대해 오해하지 않았 으면 좋겠다. 그러나 그래프에 특정 평면을 포함시키지 않으면 대답이 있다고 생각하지 않는다.

대부분의 평면 그래프가 인 경우에도 다른 가장자리가 "바깥 쪽"이되도록 노드를 재정렬 할 수 있습니다. Find border (boundary) edges of planar graph (geometric shape)을 참조하십시오. 귀하의 예는 분명히 평면이 아닙니다.

임베디드가있는 경우 볼록한 선체 점 집합과 관련되어 있습니다. Dobb 박사의 기사는 http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315입니다. "선물 포장"알고리즘은 구현하기 쉽습니다.

그러나 주어진 그래프 임베딩의 경계는 볼록하지 않을 수 있으므로 에지가 아닌 볼록 선분의 부분을 다시 계산하려면 알고리즘을 수정해야합니다. (당신은 그것을 "shrink-wrapping"알고리즘이라고 부를 수있다).

주 1 : 평면에 유일한 임베디드가 있다고 생각할 수있는 유일한 그래프 클래스는주기 그래프입니다. 다른 사람들도 쉽게있을 수 있습니다. (편집 : 최소한 경계와 관련하여 고유, 시계 방향 또는 시계 반대 방향으로 순환을 임베드 할 수 있음)

Answer 2

그래프는 단순히 정점 세트와 가장자리 세트입니다. 그래프에 내재 된 "외부 가장자리"라는 개념은 없습니다. 예를 들어 그래프에서 예로 든 것처럼, 오각형을 형성하는 모서리는 내부로 이동할 수 있습니다.