평면 그래프의 최소 사이클 기준을 찾는 알고리즘

Question

모든 노드가 (X, Y) 좌표를 나타내는 평면 그래프가 있습니다. 가장자리는 평면에서 절대로 교차하지 않습니다. 그래프는 도시의 도로를 나타냅니다. 최소한의 사이클 기준, 즉 둘러싸인 영역을 찾는 데 사용할 수있는 알고리즘을 제공하는 Python 라이브러리가 있습니까? 또는 비교적 간단한 알고리즘 (현재 가장 큰 문제는 효율성이 아닙니다) 현재 NetworkX를 사용하고 있는데, 이는 단지 cycle_basis이지만 최소한의 주기로는 작동하지 않습니다. 내가 찾은 유일한 참고 자료는 this algorithm이지만, 이것을 전체적으로 읽거나 구현할 시간이 없습니다.

Answer 1

그래프가 실제로 도시를 대표하는 경우 대기하고, 이미 그래프를 하나 포함하고 있습니다. 그냥 그 embedding의 얼굴을 가져 가라. 하나의 얼굴을 제거 할 수는 없습니다 (최소한의 것입니다). 최소한의 사이클베이스는 독특합니다 (인용 한 종이의 첫 번째 보조 정리). 그래서 당신의 해결책이 있습니다!