평면 그래프

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

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

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

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

• 평면 그래프가 아닌 그래프의 예
• 
  꼭지점이 5개인 완전 그래프($K_{5}$)
• 
  꼭지점이 3개씩인 완전 이분 그래프($K_{3,3}$)
• 
  피터슨 그래프

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

쿠라토프스키 정리

카지미에시 쿠라토프스키의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 $K_{5}$(꼭지점이 5개인 완전 그래프)나 $K_{3,3}$(각 부분의 꼭지점이 3개씩인 완전 이분 그래프)을 세분(subdivision)으로 가지는 부분그래프가 없다는 것이다.

Klaus Wagner의 정리는 이와 비슷하지만 완전히 같지는 않다. 이 정리에 따르면 어떤 그래프가 평면 그래프일 필요충분조건은 그 그래프에 $K_{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.