1 of 21

Graph Theory��Chapter 9� Planar Graphs

大葉大學(Da-Yeh Univ.)�資訊工程系(Dept. CSIE)�黃鈴玲(Lingling Huang)

2 of 21

Outline

9.1 Properties of Planar Graphs

Ch9-2

3 of 21

9.1 Properties of Planar Graphs

Definition:

A graph that can be drawn in the plane without any of its edges intersecting is called a planar graph. A graph that is so drawn in the plane is also said to be embedded (or imbedded) in the plane.

Ch9-3

Applications:�(1) circuit layout problems

(2) Three house and three utilities problem

4 of 21

Ch9-4

Fig 9-1

(a) planar, �not a plane graph

Definition:

A planar graph G that is drawn in the plane �so that no two edges intersect (that is, G is embedded in the plane) is called a plane graph.

(b) a plane graph

(c) another�plane graph

5 of 21

Fig 9-2

Ch9-5

Definition:

Let G be a plane graph. The connected pieces of the plane that remain when the vertices and edges of G are removed are called the regions of G.

Note. A given planar graph can give rise to� several different plane graph.

R₃: exterior

G₁

R₁

R₂

G₁ has 3 regions.

6 of 21

Fig 9-2

Ch9-6

Definition:

Every plane graph has exactly one unbounded region, called the exterior region. The vertices and edges of G that are incident with a region R form a subgraph of G called the boundary of R.

G₂

G₂ has only 1 region.

7 of 21

Fig 9-2

Ch9-7

R₁

R₂

R₃

R₄

R₅

G₃

v₁

v₂

v₃

v₄

v₅

v₆

v₇

v₈

v₉

G₃ has 5 regions.

Boundary of R₁:

v₁

v₂

v₃

Boundary of R₅:

v₁

v₂

v₃

v₄

v₅

v₆

v₇

v₉

8 of 21

Ch9-8

Observe:�(1) Each cycle edge belongs to the boundary � of two regions.

(2) Each bridge is on the boundary of only one region.

(exterior)

9 of 21

pf: (by induction on q)

Ch9-9

Thm 9.1: (Euler’s Formula)

If G is a connected plane graph with p vertices, q edges, and r regions, then� p − q + r = 2.

(basis) If q = 0, then G ≅ K₁; so p = 1, r =1,� and p − q + r = 2.

(inductive) Assume the result is true for any�graph with q = k − 1 edges, where k ≥ 1.

Let G be a graph with k edges. Suppose G has�p vertices and r regions.

10 of 21

Ch9-10

If G is a tree, then G has p vertices, p−1 edges and 1 region.

⇒ p − q + r = p – (p−1) + 1 = 2.

If G is not a tree, then some edge e of G is on a cycle.

Hence G−e is a connected plane graph having �order p and size k−1, and r−1 regions.

⇒ p − (k−1) + (r−1) = 2 (by assumption)

⇒ p − k + r = 2

#

11 of 21

Ch9-11

Fig 9-4 Two embeddings of a planar graph

(a)

(b)

12 of 21

Ch9-12

Definition:

A plane graph G is called maximal planar if, for every pair u, v of nonadjacent vertices of G, the graph G+uv is nonplanar.

Thus, in any embedding of a maximal planar graph G �of order at least 3, the boundary of every region of G�is a triangle.

13 of 21

pf:

Ch9-13

Thm 9.2: If G is a maximal planar graph with p ≥ 3 vertices and q edges, then� q = 3p − 6.

Embed the graph G in the plane, resulting in �r regions.

Since the boundary of every region of G is a�triangle, every edge lies on the boundary of�two regions.

⇒

⇒ p − q + r = 2.

⇒ p − q + 2q/3 = 2.

⇒ q = 3p − 6

14 of 21

pf:

Ch9-14

Cor. 9.2(a): If G is a maximal planar bipartite graph with p ≥ 3 vertices and q edges, then q = 2p − 4.

The boundary of every region is a 4-cycle.

Cor. 9.2(b): If G is a planar graph with p ≥ 3 vertices and q edges, then� q ≤ 3p − 6.

pf:

If G is not maximal planar, we can add edges �to G to produce a maximal planar graph.

By Thm. 9.2 得證.

4r = 2q ⇒ p − q + q/2 = 2 ⇒ q = 2p − 4.

15 of 21

pf:

Ch9-15

Thm 9.3: Every planar graph contains a vertex of degree 5 or less.

Let G be a planar graph of p vertices and�q edges.

If deg(v) ≥ 6 for every v∈V(G)

2q ≥ 6p →←

⇒

16 of 21

Ch9-16

Fig 9-5 Two important nonplanar graph

K₅

K_3,3

17 of 21

pf:

Ch9-17

Thm 9.4: The graphs K₅ and K_3,3 are nonplanar.

(1) K₅ has p = 5 vertices and q = 10 edges.

(2) Suppose K_3,3 is planar, and consider any� embedding of K_3,3 in the plane.

q > 3p − 6 ⇒ K₅ is nonplanar.

Suppose the embedding has r regions.

p − q + r = 2 ⇒ r = 5

K_3,3 is bipartite �⇒ The boundary of every region has ≥4 edges.

⇒

→←

18 of 21

Ch9-18

Definition:

A subdivision of a graph G is a graph obtained by inserting vertices (of degree 2) into the edges of G.

注意：此定義與 p. 31 中定義 G 的subdivision graph 為在 G 的每條邊上各加一點並不相同。

19 of 21

Ch9-19

Fig 9-6 Subdivisions of graphs.

G

H

F

H is a subdivision of G.

F is not a subdivision of G.

20 of 21

Ch9-20

Fig 9-7 The Petersen graph is nonplanar.

(a) Petersen

Thm 9.5: (Kuratowski’s Theorem)�A graph is planar if and only if it contains no subgraph that is isomorphic to or is a subdivision of K₅ or K_3,3.

(b) Subdivision of K_3,3

1

2

3

6

5

4

1

2

3

4

5

6

7

8

9

10

21 of 21

Homework

Exercise 9.1:� 1, 2, 3, 5

Ch9-21