[자료구조] Planar graph 와 plane graph

그래프는 다양합니다. planar graph 와 plane graph에 대해서 알아보겠습니다.

 

Planar graph

정의는 다음과 같습니다.

a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. (위키피디아)

그래프를 구성하는 모든 edge가 서로 크로스 하지 않는 그래프군요. 그러나 이 점만 생각하면 안됩니다. 만약 해당 그래프를 다시 그릴 때 edge 끼리 크로스하지 않을 수 있을 때, 해당 그래프 또한 planar graph 입니다.

따라서 아래 그래프는 planar graph 입니다. 다시 그릴 때 모든 edge 가 크로스하지 않게 그릴 수 있기 때문이죠.

 

Plane graph

그럼 위 그래프의 모든 edge 가 크로스하지 않도록 다시 그려보면 아래와 같이 그릴 수 있습니다.

이게 plane graph 입니다.

 

Planar graph 가 아닌 것

절대 plane graph가 될 수 없는 그래프들도 존재합니다. 아래와 같은 그래프가 있습니다.  

 

출처

https://discrete.openmathbooks.org/dmoi3/sec_planar.html

http://www.math.caltech.edu/~2014-15/2term/ma006b/08%20Planar1.pdf