평면 그래프 (Planar Graph)
한 줄 정의: 간선끼리 교차하지 않도록 평면 위에 그릴 수 있는 그래프를 말합니다.
쉽게 풀면
점과 선으로 이루어진 그래프를 종이에 그릴 때, 선이 서로 겹치지 않게 그릴 수 있으면 평면 그래프입니다. 처음 그림에서 선이 겹쳐도 다시 배치해 겹치지 않게 할 수 있으면 평면 그래프입니다. 세 집에 전기·가스·수도를 겹치지 않게 연결하는 퍼즐이 불가능한 이유도 이 개념으로 설명됩니다.
왜 중요한가
회로 기판 배선, 지도 채색, 네트워크 시각화처럼 교차를 피해야 하는 문제의 이론적 기반입니다. 평면 그래프에서만 성립하는 효율적 알고리즘도 많습니다.
논문에서는 이렇게 쓰입니다
"완전그래프 K₅와 완전이분그래프 K₃,₃는 평면 그래프가 아니므로, 이를 포함하는 회로는 단층 기판에 교차 없이 배선할 수 없다."
쿠라토프스키 정리를 응용한 예시입니다.
조금 더 깊게 보면
연결된 평면 그래프에서는 꼭짓점 수 V, 간선 수 E, 면 수 F 사이에 V−E+F=2(오일러 공식)가 성립합니다. 여기서 꼭짓점이 3개 이상인 단순 평면 그래프는 E≤3V−6을 만족한다는 부등식이 나옵니다. 쿠라토프스키 정리는 그래프가 K₅나 K₃,₃의 세분을 포함하지 않을 때에만 평면 그래프라고 특징짓습니다. 사색정리는 모든 평면 그래프의 꼭짓점을 네 가지 색으로 인접한 것끼리 다르게 칠할 수 있다는 결과입니다.
주의할 점
미술 비평의 '평면성'(그린버그)은 회화 매체의 성질에 관한 개념으로 이 항목과 무관합니다. 이미 교차 없이 그려진 그림(평면 임베딩)과 그렇게 그릴 수 있는 그래프를 구분해 쓰기도 합니다.