그래프이론 (Graph Theory) 에 관한 글이다. 이번 글에서는 Planar Graphs, drawing, embedding, plane graph, faces, dual graph에 대해 알아보겠다. Planar Graphs, drawing, embedding, plane graph, faces, dual graph는 중요한 개념이니 하나씩 보도록 하자.
Drawing 과 crossing
Drawing 과 crossing 의 개념에 대해 알아보자. curve, polygonal curve, polygonal u,v-curve 등을 먼저 알아본 이후에 drawing 과 crossing에 대해 알아보자.
curve, polygonal curve, polygonal u,v-curve
curve는 [0,1] 에서 \mathbf{R} 가는 continuous function 의 이미지이다.
polygonal curve는 curve인데 유한개의 직선이 이어진 형태의 curve를 말한다.
polygonal u,v-curve 는 끝점이 u,v인 polygonal curve를 말한다.
Drawing
그래프 G 가 있다고 하자. 이 때 정의역을 V(G) \cup E(G) 로 갖는 아래의 조건을 만족하는 f 를 drawing 이라고 한다.
1. v \in V(G) 에 대하여 f(v) 는 \mathbf{R}^2 의 점
2. uv \in E(G) 에 대하여 f(uv) 는 polygonal f(u),f(v) curve
1. 의 의미는 vertex는 평면위의 점으로 mapping 한다는 것이고 2. 의 의미는 edge는 매핑된 점들을 잇는 curve라는 얘기이다.
Crossing
두개의 서로다른 e,e^\prime \in E(G) 가 있을 때 f(e), f(e^\prime) 의 끝점이 아니면서 f(e) \cap f(e^\prime) 에 속하는 point 를 crossing 이라 한다. 두 edge가 끝점을 제외하고 만난다면 (교차한다면) crossing 이라고 부른다.
Planar graph
이제 planar graph에 대해 알아보자.
planar embedding
어떤 graph G 가 있다고 하자. 이 G에 대하여 crossing 이 없는 drawing 이 존재한다면 이 그래프 G가 planar라고 말한다. 혹은 planar graph 라고 말한다. 그리고 이렇게 그래프 G를 planar 하게 만드는 drawing 을 planar embedding 이라고 한다.
plane graph
그래프 G가 있고 planar embedding f 가 있다고 하자. 이 때 f(G)를 plane graph 라고 한다.
closed
curve 의 끝점이 서로 같다면 curve를 closed라고 부른다.
simple
curve 인데 끝점을 제외하고 반복되는 점이 없다면 simple curve 라고 한다.
face
이제 face에 대해 알아보자. 쉽게 말하면 plane graph 가 있다고 할 때 이 plane graph 의 curve들이 나누어 버리는 면들을 의미한다.
open set
집합 U가 있을 때 이 U의 모든 원소에 대하여 이 원소를 포함하는 open ball 을 만들 수 있고 이 open ball이 open set의 부분집합이라면 U를 open set이라고 부른다.
region
집합 U가 있다고 하자. U위의 어떤 두점을 고르더라도 이 두점을 잇는 polygonal curve를 갖고 있다면 이 집합을 region 이라고 한다.
face에 대해
어떤 그래프 G가 있다고 하자. 그리고 G를 planar하게 만드는 planar embedding f 가 있다고 하자. f(G)와 교점이 없는 maximal한 region 을 face라고 한다. 말이 어려운데 그냥 plane graph가 만드는 면들을 말한다.
Dual graph
그래프 G가 있다고 하자. G는 plane graph 라고 하자. 이제 새로운 그래프 G*를 정의할 것이다. G*의 vertices가 G의 face들로 구성되어있다. G의 두 face x,y 가 하나의 curve를 두고 맞닿아 있을 때 G*의 edge xy를 정의한다. 이러한 graph G*를 그래프 G의 dual graph 라고 부른다. face가 두개 있고 이 두 face 사이에 강이 있어서 강만 건너가면 바로 두 face간을 이동할 수 있을 때 dual graph 라고 부른다.