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

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

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

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

쿠라토프스키 정리편집

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

성질편집

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

 

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

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

외부 링크편집