평면 그래프

평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다.

예를 들어 다음의 그래프는 모두 평면 그래프이다.

• 평면 그래프의 예
• 
• 
  이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다.
• 
  앞의 그래프와 같은 그래프이다.

한편 아래 그래프는 평면 그래프가 아니다.

• 평면 그래프가 아닌 그래프의 예
• 
  꼭짓점이 5개인 완전 그래프($K_{5}$)
• 
  꼭짓점이 3개씩인 완전 이분 그래프($K_{3,3}$)
• 
  페테르센 그래프

엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다.

쿠라토프스키 정리

카지미에시 쿠라토프스키의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 $K_{5}$(꼭짓점이 5개인 완전 그래프) 또는 $K_{3,3}$을 마이너로 갖지 않는다는 것이다.

성질

평면 그래프의 오일러 지표는 2이다. 즉, 꼭짓점의 수를 $v$, 변의 수를 $e$, 면의 수를 $f$라고 하면, 평면 그래프의 경우 다음의 식이 성립한다.

$v-e+f=2$

이때 면은 변으로 닫힌 유한한 넓이의 면뿐만이 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K₃ 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다.

4색정리에 의하면, 평면 그래프에서는 인접한 두 꼭짓점이 다른 색을 갖도록 4개의 색깔로 꼭짓점을 칠할 수 있다.

외부 링크

• “Graph, planar”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Planar graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Nonplanar graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Planar connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Kuratowski reduction theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.