Graph Theory

Planar Graphs
by
I V V RAO

1
Graph Theory

Drawings in the plan

 Can a graph be drawn in a plane without edge crossings?

2
Ch. 6. Planar Graphs
Graph Theory

Proposition 6.1.2: K5 and K3,3 cannot be

drawn without crossings
Proof:
 Considers a drawing of K5 or K3,3 in the plane.
 Let C be a spanning cycle. 
B
A E
A C A C
E B

D F D
F
C B
D E

3
Ch. 6. Planar Graphs
Graph Theory

Proposition 6.1.2: K5 and K3,3 cannot be

drawn without crossings
Proof: (continue)
 If the drawing does not have crossing edges,
– then C is drawn as a closed curve.
– Chords of C must be drawn inside or outside this curve.
 Two chords conflict if their endpoints on C occur in alternating
order.
 When two chords conflict, we can draw only one inside C and
one outside C. 
A

E B
Chord
D C
4
Ch. 6. Planar Graphs
Graph Theory

Proposition 6.1.2: K5 and K3,3 cannot be

drawn without crossings Continued

Proof: continued
 A 6-cycle in K3,3 has three pairwise conflicting
chords.
 We can put at most one inside and one outside,
– so it is not possible to complete the embedding.
 When C is a 5-cycle in K5, at most two chords can go
inside or outside.
– Since there are five chords, again it is not possible to
complete the embeddings.
 Hence neither of these graphs is planar.
5
Ch. 6. Planar Graphs
Graph Theory

Curve, Drawing 6.1.3

 A curve is the image of a continuous map from [0, 1] to R2.

 A polygonal curve is a curve composed of finitely many line
segments.
– It is a polygonal u, v-curve when it starts at u and ends at v.
 A drawing of a graph G is a function f defined on V(G)∪E(G)
that assigns each vertex v a point f(v) in the plane and assigns
each edge with endpoints u, v a polygonal f(u), f(v)-curve.
– The images of vertices are distinct.
– A point in f(e)∩f(e’) that is not a common endpoint is a crossing.

6
Ch. 6. Planar Graphs
Graph Theory

Planar Graph, Plane Graph

 A graph is planar if it has a drawing without crossings.
– Such a drawing is a planar embedding of G.
 A plane graph is a particular planar embedding of a
planar graph.
 A curve is closed if its first and last points are the same.

– It is simple if it has no repeated points except possibly

first = last.
 A planar embedding of a graph cuts the plane into
pieces.
– These pieces are fundamental objects of study.
7
Ch. 6. Planar Graphs
Graph Theory

Face 6.1.5

 An open set in the plane is a set U  R2 such that for every p

 U, all points within some small distance from p belong to
U.
 A region is an open set U that contains a polygonal u,v-curve
for every pair u,v  U.
 The faces of a plane graph are the maximal regions of the
plane that contain no point used in the embedding.

A face

Totally, 4 faces

8
Ch. 6. Planar Graphs
Graph Theory

Dual Graph
 The Dual graph G* of a plane graph G is a plane graph
 The vertices of G* correspond to the faces of G.
 The edges of G* correspond to the edges of G as follows:
– if e is an edge of G with face X on one side and face Y on the
other side, then the endpoints of the dual edge e*⊆E(G*) are
the vertices x, y of G* that represent the faces X, Y of G.

– The order in the plane of the edges incident to x⊆V(G*) is the
order of the edges bounding the face X of G in a walk around its
boundary.

9
Ch. 6. Planar Graphs
Graph Theory

Face and its length 6.1.11

 The length of a face in a plane graph G is the total

length of the closed walk(s) in G bounding the face.

10
Ch. 6. Planar Graphs
Graph Theory

Proposition 6.1.13: If l(Fi) denotes the length of face

Fi in a plane graph G, then 2e(G)=  l(Fi).
Proof:
 The face lengths are the degrees of the dual vertices.
Since e(G)=e(G*), the statement 2e(G)= l(Fi) is thus
the same as the degree-sum formula 2e(G*)= dG* (x)
for G*. (Both sums count each edge twice.)

l=4
l=5
e(G) = 6
l=3  l(Fi) = 12

11
Ch. 6. Planar Graphs
Graph Theory

Theorem6.1.14: Edges in a plane graph G form a cycle in G if

and only if the corresponding dual edges form a bond in G*.

Proof:
 Recall that a bond is a minimal nonempty edge cut.
 Consider D  E(G). If D contains no cycle in G, then
D encloses no region.
 It remains possible to reach the unbounded face of G
from every face without crossing D. Hence G*-D* is
connected, and D* contains no edge cut.

12
Ch. 6. Planar Graphs
Graph Theory

Theorem6.1.14 continued

 If D is the edge set of a cycle in G,

– then the corresponding edge set D*  E(G*) contains
all dual edges joining faces inside D to faces outside D.
– Thus D* contains an edge cut.
 If D contains a cycle and more,
– then D* contains an edge cut and more.
– Thus D* is a minimal edge cut if and only if D is a
cycle.

13
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.16

The following are equivalent for a plane graph G.

 A) G is bipartite.
 B) Every face of G has even length.
 C) The dual graph G* is Eulerian.

14
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.16 Continued

Proof: AB
 A face boundary consists of closed walks.
 Every odd closed walk contains an odd cycle.
 Therefore, in a bipartite plane graph the
contributions to the length of faces are all even.

15
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.16 Continued

Proof: BA
 Let C be a cycle in G. Since G has no crossings, C is laid
out as a simple closed curve; let F be the region enclosed
by C.
 Every region of G is wholly within F or wholly outside F.
 If we sum the face lengths for the regions inside F, we
obtain an even number, since each face length is even.
 This sum counts each edge of C once. It also counts each
edge inside F twice, since each such edge belongs twice
to faces in F. Hence the parity of the length of C is the
same as the parity of the full sum, which is even.

16
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.16 Continued

Proof: BC.
 The dual graph G* is connected, and its vertex degrees
are the face lengths of G.

17
Ch. 6. Planar Graphs
Graph Theory

Outerplanar
 A graph is outerplanar if it has an embedding with
every vertex on the boundary of the unbounded face.
 An outerplane graph is such an embedding of an
outerplanar graph.

18
Ch. 6. Planar Graphs
Graph Theory

Proposition: K4 and K2,3 are planar but not

outerplanar 6.1.19
Proof:
 The figure below shows that K4 and K2,3 are planar.

19
Ch. 6. Planar Graphs
Graph Theory

Proposition: K4 and K2,3 are planar but not

outerplanar 6.1.19
Proof: Continued
 To show that they are not outerplanar, observe that
they are 2-connected. Thus an outerplane embedding
requires a spanning cycle. There is no spanning cycle
in K2,3, since it would be a cycle of length 5 in a
bipartite graph.
 There is a spanning cycle in K4, but the endpoints of
the remaining two edges alternate along it. Hence
these chords conflict and cannot both be drawn
inside. Drawing a chord outside separates a vertex
from the outer face.
20
Ch. 6. Planar Graphs
Graph Theory

Euler’s Formula: If a connected plane graph G has exactly n

vertices, e edges, and f faces, then n-e+f=2. 6.1.21

Proof: We use induction on n.

 Basis step (n=1): G is a “bouquet” of loops, each a closed
curve in the embedding.
 If e=0, then f=1, and the formula holds.
 Each added loop passes through a face and cuts it into
two faces. This augments the edge count and the face
count each by 1. Thus the formula holds when n =1 for
any number of edges.

n=1 n=1
e=1 e=2
f=1 f=3

21
Ch. 6. Planar Graphs
Graph Theory

Euler’s Formula 6.1.21 continued

 Induction step (n>1): Since G is connected, we can find

an edge that is not a loop. When we contract such an
edge, we obtain a plane graph G’ with n’ vertices, e’
edges, and f’ faces. The contraction does not change the
number of faces (we merely shortened boundaries), but it
reduces the number of edges and vertices by 1, so n’=n-1,
e’=e-1, and f’=f. Applying the induction hypothesis yields
 n-e+f=n’+1-(e’+1)+f’=n’-e’+f’=2.

22
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.23: If G is a simple planar graph with at least

three vertices, then e(G) ≤ 3n(G) - 6. If also G is triangle-free,
then e(G) ≤ 2n(G) – 4.

Proof
 It suffices to consider connected graphs; otherwise
we could add edges. Euler’s Formula will relate n(G)
and e(G) if we can dispose of f.
 Proposition 6.1.13 provides an inequality between e
and f. Every face boundary in a simple graph
contains at least three edges (if n(G)  3). Letting
{fi} be the list of face lengths, this yields 2e =  fi 
3f. Substituting into n-e+f=2 yields e ≤ 3n – 6.
23
Ch. 6. Planar Graphs
Graph Theory

Theorem 6.1.23: If G is a simple planar graph with at least

three vertices, then e(G) ≤ 3n(G) - 6. If also G is triangle-free,
then e(G) ≤ 2n(G) – 4.

Proof: Continued
 When G is triangle-free, the faces have length at least
4. In this case 2e =  fi  4f, and we obtain e  2n-
4.

24
Ch. 6. Planar Graphs
Graph Theory

Example 6.1.24
 Nonplanarity of K5 and K3,3 follows immediately
from Theorem 6.1.23. For K5, we have
e = 10 and 3n - 6 = 9.
 Thus e > 3n – 6.
 Since K3,3 is triangle-free, we have
 e = 9 and 2n - 4 = 8.
 Thus e > 2n - 4
 These graphs have too many edges to be planar.

25
Ch. 6. Planar Graphs
Graph Theory

Maximal planar graph and Triangulation

 A maximal planar graph is simple planar graph that

is not a spanning subgraph of another planar graph.
 A triangulation is a simple plane graph where every
face boundary is a 3-cycle.

26
Ch. 6. Planar Graphs
Graph Theory

Proposition: For a simple n-vertex plane graph G,

the following are equivalent.

A) G has 3n – 6 edges.
B) G is a triangulation.
C) G is a maximal plane graph.

27
Ch. 6. Planar Graphs
Graph Theory

Characterization of Planar Graphs

 Kasimir Kuratowski [1930]
– The K in K5 stands for Kasimir, and
– the K in K3,3 stands for Kuratowski.
 He is great.

28
Ch. 6. Planar Graphs
Graph Theory

Subdivision of a Graph
 A subdivision od K3,3

29
Ch. 6. Planar Graphs
Graph Theory

Proposition: If a graph G has a subgraph that is a subdivision

of K5 or K3,3, then G is nonplanar. 6.2.1

Proof:
 Every subgraph of a planar graph is planar.
 The subdivisions of K5 and K3,3 are nonplanr.
– Because subdividing edges does not affect planarity.
 Hence, it is proved.

30
Ch. 6. Planar Graphs
Graph Theory

Kuratowski’s Theorem6.2.2

 A graph is planar if and only if it does not

contain a subdivision of K5 or K3,3

31
Ch. 6. Planar Graphs
Graph Theory

Lemma 6.2.4
 If F is the edge set of a face in a planar embedding of
G, then G has an embedding with F being the edge
set of the unbounded face

32
Ch. 6. Planar Graphs
Graph Theory

Planarity test
 Successively add paths from current fragments to
check if the graph can be drawn without crossing.

33
Ch. 6. Planar Graphs
Graph Theory

Five Color Theorem Heawood[1890]

 Every planer graph is 5–colorable.

34
Ch. 6. Planar Graphs
Graph Theory

Theorem Appel-Haken-Koch[1977] 6.3.6

 Every planar graph is 4-colorable.
– The proof used configurations with ring size up to 14.
– A ring of size 13 has 66430 distinguishable 4-
colorings
– Reducibility requires showing that each leads to a 4-
coloring of the full graph
– Using 1000 hours of computer time in 1976, they
found an unavoidable set of 1936 reducible
configurations, all with ring size at most 14

35
Ch. 6. Planar Graphs