계산 기하학의 경우 평면 직선 그래프, 줄여서 PSLG(또는 직선 평면 그래프 또는 평면 직선 그래프)는 다음과 같이 평면에 평면 그래프를 삽입하기 위해 구현된 용어로 정의됩니다. 가장자리는 직선 세그먼트로 매핑됩니다. Fáry의 정리(1948)에 대한 진술은 모든 평면 그래프에 이러한 종류의 포함이 있다는 것입니다.
계산 기하학의 경우, PSLG는 세분화가 다각형이라는 가정 또는 주장과 함께 평면 세분화라고 하는 경우가 많습니다.
1차 정점이 없으면 PSLG는 평면을 다각형 영역으로 세분화하거나 그 반대로 정의합니다. 1차 정점이 없으면 다양한 알고리즘에 대한 설명이 간단해 지지만 필수적인 것은 아닙니다.
다양한 지도의 표현은 예를 들어 지리 정보 시스템의 지리 지도와 같은 PSLG에서 제공할 수 있습니다.
PSLG에는 몇 가지 특별한 경우가 있습니다. 특별한 경우는 삼각분할(다각형 삼각분할, 점 집합 삼각분할)입니다. 점 집합 삼각 측량은 그래프를 평면으로 유지하면서 직선 모서리를 추가할 수 없다는 점에서 최대 PSLG입니다. 삼각측량은 많은 영역에서 다양한 응용이 가능합니다.
PSLG는 특별한 종류의 유클리드 그래프로 볼 수 있습니다. 또한 유클리드 그래프와 관련된 논의에서 주요 관심은 메트릭 속성, 즉 정점 사이의 거리인 반면 PSLG의 주요 관심은 토폴로지 속성입니다. Delaunay 삼각분할과 같은 일부 그래프의 경우 미터법 및 토폴로지 속성이 모두 중요합니다.
표현
PSLG는 잘 알려진 세 가지 데이터 구조로 표시됩니다. 이러한 데이터 구조는 Winged-edge 데이터 구조, Halfedge 및 Quadedge입니다. Winged-edge 데이터 구조는 세 가지 중 가장 오래된 것이지만 이를 조작하려면 복잡한 대소문자 구분이 필요한 경우가 많습니다. 그 에지 참조 뒤에 있는 이유는 에지 방향을 저장하지 않으며 면 주변의 에지의 방향이 일치할 필요가 없습니다. 하프 에지 데이터 구조는 에지의 두 방향을 모두 저장하고 적절하게 연결하여 작업과 저장 체계를 단순화하는 데 유용합니다. Quadedge 데이터 구조는 평면 세분화와 이중 분할을 동시에 저장하는 데 유용합니다. 그것의 기록은 명시적으로 각 edge당 4개의 edge 기록으로만 구성되며 단순화된 형태로 PSLG를 저장하는데 유용하다.