[Graph Theory] Planar Graph, subdivisions and minors

그래프를 종이에 그릴 수 있겠니? 선이 겹치면 헷갈리잖아. 규칙을 몇 개 정해줄게.

 

Definition

Drawing a multigraph

두 edge 를 crossing: 공통의 internal point 가진다는 것

emdgedding: crossing 이 없는 drawing

planar: multigraph 가 plane 에 embed 가능

plane multigraph: multigraph 를 planar embedding 하게 그린 예시

"안겹치게 잘 그려봐"

 

Proposition

$K_5$ 랑 $K_{3, 3}$ 은 planar 그래프가 아니다.

5개짜리 complete graph 랑 3대3 complete bigraph 는 안겹치고는 못 그린다.

$\textit{Proof}$

$C$ 라는 spanning cycle, 그러니까 Hamiltonian cycle 을 생각하자. $C$ 는 close curve로 그려지고, 여기에 chord 가 안이나 밖에 그려진다. 이렇게되면 2개의 chord 가 번갈아가면서 한 공간에 있으면 겹치게 되니, 안이나 밖에 하나씩 밖에 못 그린다.

$K_{3,3}$은 6짜리 cycle 이 있고, 세 쌍으로 chord가 나와서 겹친다. 하나는 안에 그린다 쳐도 밖에서 2개가 걸친다. $K_5$도 5짜리 cycle이 나오는데, chord가 겹친다.

 

여기서 우리는 cycle 이 plane을 두 개의 파트로 나눈다는 걸 알 수 있다 (안과 밖)

편의상 이 컨셉을 "Face"라고 부르고, planar multigraph 의 embedding 은 plane 을 face로 cut 한다.

face 는 special open sets in $\mathbf{R}^2$ 다.

open set이라 함은 a set $U \subseteq \mathbf{R}^2$ such that for any $p \in U$에 대해서 모든 포인트가 $p$로부터 small distance 내에 있고, $U$에 포함되는 경우.

 

Definition

region: $U$ 안의 모든 2개의 포인트가 $U$ 안의 curve 내에 있도록 하는 open set $U$. 같은 curve로 나뉘는 open set

face: edge 로 인해 disjoint 되는 maximal region. region 중에서 가장 넓게 가져가면

curve is closed: 처음과 마지막 포인트가 같고 simple 하고.

 

Fact.

모든 plane multigraph with finitely many edge 는 하나의 unbounded face 를 가진다.

 

Theorem <Restricted Jordan Curve theorem>

<Simple closed polygonal> curve $C$ 는 plane 을 정확히 두 개의 face로 나누고, 걔들은 $C$ 를 boundary 로 가진다.

closed curve 는 2개의 face를 만든다.

$\textit{Proof}$

$C$ 는 유한 개의 segment를 가지고 <polygonal이라서>, 

$C$의 "오른쪽" 에 매우 가까운 점들을 생각할 수 있고 <vector dot product 로 "오른쪽"을 정의 가능>

마찬가지로 "왼쪽" 에도 그런 점들이 있다. locally 이렇게 나눌 수 있고, globally 하게 적용하려면

rays in the plane 을 생각한다.

$C$ 가 아닌 포인트 $p$로부터의 ray $\rho$ 를 생각했을 때, $f(\rho)$ 를 $C$와 $\rho$가 겹치는 point 갯수라고 생각해보자.

$f(\rho)$ 는 $C$의 segment 의 endpoint 랑 만날 때에만 바뀐다.

하지만 그 홀짝성은 밖에서 긋는거랑 안에서 긋는거랑 동일하다.

any two points in the same face have equal pairity.

이렇게 inside 와 outside 를 구분할 수 있다.

 

Definition

$\textit{dualG}^*$: $G$의 face 들을 vertex로, 그에 대응되는 $G$의 edge들을 edge로 가지는 그래프. face를 점으로 바꾸고 edge는 대응

embedding of $G^*$: 각 face X마다 vertex x를 안에 두고 X를 감싸는 boundary 를 기준으로 X에서 x로 가는 curve 를 edge로 추가.

 

Fact:

$(G^*)^*$ 는 isomorphic to $G$ $\Leftrightarrow$ $G$ is connected

Connected graph 에서 face의 boundary 는 closed walk.

 

Definition

Length of a face: face의 boundary 를 그리는 closed walk 의 total length. face를 감싸는 closed walk의 길이

이게 사실 dual graph 로 넘어가면 degree of vertices 다.

 

Proposition

$l(F)$ 가 length of face $F$ 이고 plane multigraph $G$ 가 $m$개의 edge를 가지면,

$2m = \sum_{F}l(F)$

모든 face 의 length 합은 edge 갯수의 2배다.

$\textit{Proof}$

일단 $|E(G)| = |E(G^*)|$고, handshake lemma.

 

Definition

bond: 없어지면 component 의 갯수를 늘리는 minimal edge set. 몇 개 없어져야 끊어지느냐

 

Theorem

plane multigraph $G$ 에서 edge들이 cycle 을 만든다 $\Leftrightarrow$ edge들이 $G^*$ 에서 bond를 만든다.

cycle 과 bond 는 dual 에서 대응 관계다.

$\textit{Proof}$

$D \subseteq E(G)$ 에서 만약 $D$ 가 cycle 이 없다 치자. 그러면 $D$는 region 을 못 만든다.

$D$ 랑 안만나고도 unbounded face 끼리 만날 수 있으니, $G^* - D^*$ 는 connected, 그래서 $D^*$는 edge cut도 없다.

만약 $D$가 cycle에 포함된다면 이에 대응되는 $D* \subseteq E(G^*)$는 $D$의 안쪽 face랑 바깥쪽 face 를 이어주는 edge 들이 된다. 이 때 $D^*$가 edge cut 이다.

 

Theorem <Euler's formula>

connected plane multigraph $G$

$v - e + f = 2$

vertex 랑 face 더한 거랑 edge 갯수는 2개 차이다.

$\textit{Proof}$

Induction on $v$.

If $v=1$, 딱 $e$로 만들어진 loop 밖에 없으니 $e+1$ faces가 있어서 성립

If $v>1$, $G$가 connected니까 loop가 아닌 edge가 분명 있다.

이걸 contract해서 나온 $G'$에서는 $v'=v-1$ 이고 $e'=e-1$이다.

그런데 face의 갯수는 차이가 없다. 그래서 $f'=f$가 된다.

induction 쓰면 $v-e+f=2$가 나온다.

 

Theorem.

G가 planar n-vertex graph (multi 아님) 이고 edge 갯수가 m개.

$n \geq 3$ $\Rightarrow$ $m \leq 3n-6$

$G$ 가 triangle-free $\Rightarrow$ $m \leq 2n-4$

planar graph 일 경우, vertex 갯수와 triangle free 여부에 따라서 edge 갯수의 상한이 있다.

우리는 connected graph 만 고려하면 된다. 그게 아니면 거기에다가 edge를 추가만 하면 되니까 <???>

$f$ 가 어떤 그래프 $G$의 embedding 에서 face 갯수라고 하면 Euler's formula 는 $n$과 $m$을 준다.

connected plane graph 의 모든 face boundary 는 길이가 최소 3이다.

$\{f_i\}$ 가 face 길이들 모음이라고 했을 때, $2m = \sum f_i \geq 3f$ 가 나온다. 여기에 $n-m+f=2$ 대입하면 $m \leq 3n-6$ 나옴.

$G$가 triangle free 면 모든 face의 길이가 최소 4니까 $2m \geq 4f$가 되면서 $m \leq 2n-4$.

 

Definition

outerplanar: multigraph 의 모든 vertex가 unbounded face 의 boundary 위에 있을 때. 바깥으로 vertex를 싹 밀 수 있을 때

outerplane multigraph: outerplanar 한 embedding 을 가진 multigraph

 

Proposition

$K_4$와 $K_{2,3}$ 은 planar이지만, outerplanar 하지는 않다.

embedding 을 위해 밖으로 싹 밀어도 안쪽에 무조건 최소 한 개 vertex 남는다.

$\textit{Proof}$

일단 planar 함은 보이기가 쉽고,

outerplanar 인걸 보이려면 2-connected 임을 보여야 한다. 그러니까 spanning cycle도 있어야 한다.

일단 $K_{2,3]$은 spanning cycle 이 없다.

$K_4$는 spanning cycle이 있지만, 남은 2개의 edge가 번갈아가면서 나오면서 chord conflict 발생.

 

 

7.2 Subdivisions and minors

 

Definition

subdivision of $F$, $F$-subdivision: 그래프 $F$의 edge에 subdivision 을 먹여서 나온 그래프. edge에 분절점을 추가해서 더 끊어지게 만든, 그러나 원형은 보존한.

Branch vertices of $H$: $\delta(F) \geq 3$인 $F$를 subdivision 해서 얻은 $H$에서, degree가 최소 3인 edge. 분절점 추가 안한 vertex.

Images of vertices of $F$: branch vertices 들.

 

$H$ is a minor of $G$, $G$ contains $H$-minor: $G$에서 edge나 vertex를 뺴서, 또는 edge를 contracting 해서 $H$를 얻을 경우. $G$를 압축하고 압축하면 $H$가 나옴.

$H$ is a topological minor of $G$, $G$ contains $H$-topological minor: $G$ 가 $H$의 subdivision 을 subgraph 로 가짐. $G$ 안에 $H$ 요소가 있음.

minor 느낌을 가지고 있으면 planarity 가 유지된다

Fact.

Minor relation preserves planarity. 그림 상으로는 뭐 그대로 유지되겠지.

 

Proposition

$G$ contain $K_5$-minor or $K_{3,3}$-minor $\Rightarrow$ $G$ 는 nonplanar

$K_5$나 $K_{3,3}$ 의 느낌만 있으면 $G$도 nonplanar다.

 

Theorem <Wagner>

Graph가 planar $\Leftrightarrow$ $K_5$ 나 $K_{3,3}$ 을 minor로 안가진다.

 

stronger theorem 도 먹힌다.

 

Theorem <Kuratowski>

Graph 가 planar $\Leftrightarrow$ $K_5$나 $K_{3,3}$ 을 subdivision 으로도 안 가진다.

 

Definition

Kuratowski subgraph: $K_5$거나 $K_{3,3}$ 의 subdivision 을 subgraph. 잘 찾아봤더니 $K_5$랑 $K{3,3}$ 느낌이 있는 subgraph

$G[C \cup S]$, S-lobe of $G$: $G$ 의 seperating set $S$. 떨어져나오면 $G$를 끊어버리는 vertex set

 

Lemma

$F$가 $G$의 embedding에 있는 face의 edge set $\Rightarrow$ $G$ 는 $F$가 unbounded face의 edge set이 되는 embedding을 가진다.

$f$ 가 지금은 bound 같지? 어딘가에 unbound 하는 방법이 있어.

$\textit{Proof}$

embeding 을 구<sphere>에 투영해보자.

구를 뒤집으면 unbounded가 된다.

 

Lemma

모든 minimal nonplanar graph 는 2-connected다.

nonplanar graph 를 줄이고 줄이면 2-connected 나온다.

$\textit{Proof}$

$G$가 minimal nonplanar graph 라 치자.

$G$가 disconnected면, 한 component를 잘 그리고, 나머지 하나를 face 하나에 작게 그려넣으면 된다.

$G$가 cut-vertex $v$를 하나 가진다 치고, $\{v\}$-lobs 로 $G_1, ..., G_k$가 있다고 치자.

minimality 가 있으니 $G_i$도 planar다.

우리는 $v$에다가 $G_i$ 를 outside face에 그릴 수 있다 by previous lemma

각 $G_i$ embedding 을 $360/k$ 각 내에 그리면 embedding을 그릴 수 있다.

그래서 0, 1-connected 일 때에는 planar하다.

 

Lemma

$\{x,y\}$ 가 $G$의 seperating set이고, $G_1, ..., G_k$ 가 $\{x,y\}$-lobes of $G$니까 $H_i = G_i \cup xy$라고 하자.

$G$가 nonplanar $\Rightarrow$ Some $H_i$ 가 nonplanar

$\textit{Proof}$

만약 $H_i$가 planar 면, $xy$를 outside face에 embeds 할 수 있다. 

xy가 포함된 face에다가 계속 붙여서 그려나갈 수 있다. $xy$ 가 $E(G)$에 없을 경우 삭제한다. 이러면 planar embeding of $G$를 가진다.

 

Lemma

$G$ 가 모든 $K_5$ 나 $K_{3,3}$ 을 topological minor 로 가지지 않은 모든 nonplanar graph 중에서 가장 적은 수의 edge를 가진다 $\Rightarrow$ $G$는 3-connected다.

$K_5$랑 $K_{3,3}$을 피해서 줄이고 줄이면 3-connected가 나온다.

$\textit{Proof}$

edge를 없애도 $G$에서 $K_5$나 $K_{3,3}$의 subdivision 은 안생긴다.

edge하나를 줄여도 plana subgraph 가 나오고, $G$ 는 minimal nonplanar인데다가 2-connected다.

If $G$ is not 3-connected, $S=\{x,y\}$ 가 seperating 2-set이라 하자.

$G$가 nonplanar니까 $G'\cup xy$ 도 nonplanar다. <????>

$H = G' \cup xy$라고 하면 #H#가 edge가 더 적으니 $H$ 는 Kuratowski subgrpah $F$를 가진다 <????????>

모든 $F$ 는 $xy$를 제외한 $G$에서 나올 가능성이 있다 <???????>

$S$ 가 minimal vertex cut이니까 $x$랑 $y$는 모든 S-lobe 에 neighbor가 있다.

그러니까 $F$의 $xy$를 다른 S-lobe 까지 엮는 $x,y$-path 를 만들면 Kuratowski subgraph가 나온다 <?????????????????????>

the contradiction 은 $G$의 가정에서 나오므로, $G$는 seperating 2-set을 가지지 않는다.

 

그러니까, $G$가 3-connected 라고 가정 하면, 우리는 3-contractible edge 를 찾아서 이걸 contract 하면 된다. 

 

Lemma

$G/xy$ 가 Kuratowski subgraph 를 가진다 $\Rightarrow$ $G$ 가 Kuratowski subgraph 를 가진다

contract 한 애가 kuratowski를 가지면, xy를 늘려도 여전히 가지고 있다.

$\textit{Proof}$

$H$가 $G/xy$의 Kuratowski subgraph 라고 치고, $z$가 $xy$를 contract해서 생긴 vertex라 하자.

If $z$ is not in $H$, $H$가 바로 $G$의 Kuratowski 다.

If $z \in V(H)$, 그런데 $z$가 $H$의 branch vertex가 아니면 $H$의 $z$를 $x$나, $y$나, edge $xy$로 바꾸면  Kuratowski 얻을 수 있음.

If $z$ 가 $H$의 branch vertex면, $z$의 최대 1개의 incident edge 가 $G$의 $x$랑 incident 할테니 $z$를 $xy$로 연장시키면 $y$가 Kuratowski subgraph 에 대응하는 branch vertex가 된다.

Remaining cases, $H$ 가 $K_5$ subdivision 이면, $z$가 $H$의 branch vertex라 했을 때 $x,y$ 가 $G$에 incident 하고 4개 중에 2개의 edge가 $H$의 $z$에 incident.

$u_1, u_2, (v_1, v_2)$ 가 $H$의 branch vertices 이고 $z$에서  떠나느 path의 끝이 $x (y)$ in $G$에 도달한다면, 

$u_1, u_2$ path 와 $v_1, v_2$ path 를 $H$에서 지워버리는 게 $K_{3,3}$-subdivision in $G$를 만들고, 

$y, u_1, u_2$ 가 한쪽 partite, $x, v_1, v_2$가 한쪽 partite가 되면서 서로의 branch vertices가 된다.

 

Definition

Convex embedding: 모든 edge 가 straight line segment 이고 모든 face boundary 가 convex polygon 인 embedding

 

Theorem.

3-connected graph 가 Kuratowski subgraph 가 없다 $\Rightarrow$ $G$ 는 convex embedding을 가지고, 3개 vertices가 한 line 위에 있는 경우가 없다.

$\textit{proof}$

induction on $n$.

$n \leq 4$, $K_4$가 나오면서 볼록 임베딩 가능.

$n \geq 5$라 치자. 그리고 $e=xy$가 3-contractible edge여서 $G/e$가 3-connected라 치자.

$G/e$ 는 Kuratowski subgraph 를 안가지니까 induction에 의해 $H=G/e$ 는 볼록임베딩을 가진다.

$z$가 $xy$를 contract해서 생긴 vertex라 치자.

여기에서 $z$에 붙은 edge들을 없애서 생기는 subgraph 들은 $z$를 포함하는 face를 가진다.

$H-z$ 는 2-connected다. 이 face 의 boundary 를 cycle $C$라고 하자.

$z$의 모든 neighbor는 $C$위에 있다.

$H$의 convex embedding 은 $z$로부터 이 neighbor들까지 straight segment를 가진다.

$x_1, ..., x_k$를 $C$의 cyclic order라고 치자.

- $y$의 모든 neighbor는 $x_i$ to $x_{i+1}$에 달하는 $C$의 portion 위에 있다.

- $y$ 는 $u, v, w$라는 세 개의 neighbor 를 $x$랑 공유하거나 --> $x,y,u,v,w$가 $K_5$ subdivision 을 만든다

- $y$ 는 $x_i$, $x_{i+1}$ 이랑 번갈아가면서 neighbor $u, v$를 공유한다. --> $uyv, xx_ix_{i+1}$ 이랑 xy가 $K_{3,3}-subdivision을 만든다

 

Fact.

$K_{2,4}$ 는 3-connected가 아니고 convex embedding도 없다.

Fary: 모든 planar graph 는 모든 edge가 straight line segment 인 embedding을 가진다.