평면 그래프(Planar Graph)는 간선이 교차하지 않고 평면(2차원 공간) 상에 그릴 수 있는 그래프를 의미한다. 그래프 이론에서 평면 그래프는 위상 기하학 및 전기 회로 설계, 네트워크 분석 등 다양한 분야에서 활용된다.

정의

• 평면 그래프 G는 평면 위에서 간선이 교차하지 않도록 그릴 수 있는 그래프이다.
• 평면 그래프가 아닌 그래프는 비평면 그래프(Non-Planar Graph)라고 한다.

평면 그래프의 성질

평면 그래프는 다음과 같은 성질을 만족한다.

• 오일러 공식(Euler’s Formula)
  • 연결된 평면 그래프 G = (V, E, F)에 대해 다음 관계가 성립한다.
  • V - E + F = 2
  • 여기서 V는 정점(Vertex)의 수, E는 간선(Edge)의 수, F는 면(Face)의 수를 의미한다.

• 평면 그래프의 간선 수 제한
  • 간선이 많은 그래프라도 평면 그래프가 되려면 다음 조건을 만족해야 한다.
  • 임의의 단순 평면 그래프에 대해
    • E ≤ 3V - 6 (V ≥ 3일 때)
  • 삼각형 그래프(각 면이 3개의 변으로 구성됨)에 대해
    • E = 3V - 6

대표적인 평면 그래프 예시

• 완전 그래프 K₄
  • 4개의 정점이 모든 간선으로 연결된 완전 그래프는 평면 그래프이다.

• 큐브 그래프
  • 정육면체의 모서리를 정점과 간선으로 나타낸 그래프이며 평면 그래프이다.

비평면 그래프

다음 그래프들은 평면 그래프가 될 수 없다.

• 완전 그래프 K₅
  • 5개의 정점이 모두 연결된 그래프 K₅는 어떠한 방식으로도 평면에 교차 없이 그릴 수 없다.

• 완전 이분 그래프 K_3,3
  • 정점 집합이 두 그룹으로 나뉘고, 한 그룹의 모든 정점이 다른 그룹의 모든 정점과 연결된 그래프.
  • 어떠한 방식으로도 평면에서 간선이 교차하지 않도록 그릴 수 없다.

쿠라토프스키 정리 (Kuratowski’s Theorem)

• 그래프가 평면 그래프가 아니려면 K₅ 또는 K_3,3을 부분 그래프로 포함해야 한다.
• 이는 평면 그래프 판별에 활용된다.

평면 그래프의 응용

• PCB 회로 설계
  • 전자기기에서 배선이 교차하지 않도록 설계하는 데 사용된다.

• 지도 색칠 문제
  • 4색 정리(The Four Color Theorem)를 활용하여 지도를 최소한의 색으로 구분할 때 사용된다.

• 네트워크 설계
  • 도로망, 철도망 등의 네트워크 최적화에 사용된다.

같이 보기

• 그래프 이론
• 완전 그래프
• 네트워크 이론
• 4색 정리

참고 문헌

• Diestel, R. (2017). Graph Theory. Springer.