평면 직선 그래프(PSLG)란 무엇인가?
계산 기하학(computational geometry)에서 평면 직선 그래프(Planar Straight-Line Graph, PSLG)는 평면 그래프를 평면 위에 배치(매립)하면서 모든 변(edge)이 직선 선분으로 표현되도록 만든 그래프를 의미합니다. 문헌에 따라서는 '직선 평면 그래프' 또는 '평면 직선 그래프'라는 용어로도 불립니다.
파리의 정리(Fáry's theorem, 1948)에 따르면, 모든 평면 그래프는 이러한 형태의 매립을 가질 수 있습니다. 즉, 어떤 평면 그래프든 변들이 서로 교차하지 않으면서 각 변을 직선으로 그려낼 수 있다는 뜻입니다.
평면 분할(Planar Subdivision)과의 관계
계산 기하학 분야에서 PSLG는 흔히 평면 분할(planar subdivision)이라고 불리며, 이때 분할 결과가 다각형 형태라고 가정하는 것이 일반적입니다.
차수 1(degree 1), 즉 단 하나의 변으로만 다른 꼭짓점과 연결된 꼭짓점이 없는 PSLG는 평면을 여러 개의 다각형 영역으로 나누는 분할 구조를 정의하며, 그 반대로 평면의 다각형 분할 역시 PSLG로 표현할 수 있습니다. 차수 1 꼭짓점을 제외하면 다양한 알고리즘의 설명이 크게 단순해지지만, 이는 필수적인 전제 조건은 아닙니다.
PSLG의 활용 분야
PSLG는 다양한 종류의 지도(map)를 표현하는 데 활용될 수 있습니다. 대표적인 예로 지리 정보 시스템(GIS)에서 지리적 지도를 저장하고 처리하는 작업에 널리 사용됩니다.
특수 사례: 삼각분할(Triangulation)
PSLG에는 몇 가지 특수한 경우가 있는데, 대표적인 것이 삼각분할(triangulation)입니다. 삼각분할은 다시 다각형 삼각분할(polygon triangulation)과 점 집합 삼각분할(point set triangulation)로 나눌 수 있습니다.
점 집합 삼각분할은 최대(maximal) PSLG에 해당합니다. 즉, 그래프의 평면성을 유지하면서 더 이상 새로운 직선 변을 추가할 수 없는 상태를 의미합니다. 삼각분할은 컴퓨터 그래픽스, 유한요소해석, 지형 모델링 등 수많은 분야에서 폭넓게 응용되고 있습니다.
유클리드 그래프와의 비교
PSLG는 유클리드 그래프(Euclidean graph)의 한 종류로 볼 수 있습니다. 다만 일반적인 유클리드 그래프 논의에서는 꼭짓점 간 거리와 같은 메트릭(metric) 속성이 주된 관심사인 반면, PSLG에서는 변과 면의 연결 관계 같은 위상(topological) 속성이 더욱 중요하게 다뤄집니다.
다만 델라우니 삼각분할(Delaunay triangulation)과 같은 일부 그래프에서는 메트릭 속성과 위상 속성이 모두 중요한 의미를 가집니다.
PSLG를 표현하는 3가지 자료 구조
PSLG는 잘 알려진 세 가지 자료 구조로 표현할 수 있습니다.
1. 윙드 엣지(Winged-edge) 자료 구조
세 구조 중 가장 오래된 방식입니다. 그러나 변 참조가 변의 방향 정보를 저장하지 않고, 하나의 면을 둘러싼 변들의 방향이 일관되지 않기 때문에 실제 조작 과정에서 복잡한 경우 구분(case distinction)이 자주 필요하다는 단점이 있습니다.
2. 하프엣지(Halfedge) 자료 구조
하프엣지 구조는 하나의 변에 대해 양방향 정보를 모두 저장하고 이를 적절히 연결합니다. 덕분에 연산이 단순해지고 저장 방식도 깔끔해져, PSLG 처리에 매우 유용하게 사용됩니다.
3. 쿼드엣지(Quadedge) 자료 구조
쿼드엣지 구조는 평면 분할과 그 쌍대 그래프(dual graph)를 동시에 저장할 수 있다는 점이 특징입니다. 레코드가 오직 변 레코드로만 구성되며(각 변당 4개), 단순화된 형태로 PSLG를 저장하는 데 유용합니다.
마무리
PSLG는 평면 그래프를 직선으로 표현하는 강력한 도구로, 지리 정보 시스템부터 삼각분할 알고리즘까지 다양한 분야의 기반이 됩니다. 윙드 엣지, 하프엣지, 쿼드엣지 세 가지 자료 구조의 특성을 제대로 이해하면 상황에 맞는 최적의 표현 방식을 선택할 수 있습니다.