PLANAR

GRAPHS
Module 4
 PLANAR GRAPHS
• A graph G is said to be planar if there exists some geometric representation of G
which can be drawn on a plane such that no two of its edges intersect.

• A graph that cannot be drawn on a plane without a crossover between its edges is
called nonplanar.

• A drawing of a geometric representation of a graph on any surface such that no

edges intersect is called embedding.

• A graph G is nonplanar, with all possible geometric representations, it can not be

embedded in a plane.

• A geometric graph G is planar if there exists a graph isomorphic to G that is

embedded in a plane. Otherwise, G is nonplanar.

• An embedding of a planar graph G on a plane is called a plane representation of G.

PLANAR GRAPHS
NON-PLANAR GRAPHS
 COMPLETE GRAPHS AND PLANAR

▪▪K1, K2, K3, and K4 are all planar.

▪▪Ex 11.16: Is K5 Planar?

 KURATOWSKI’S TWO GRAPHS: K5, K3,3
THEOREM 5-1: K5

The complete graph of five vertices is nonplanar.

 BIPARTITE GRAPHS
▪▪ G=(V,E) is bipartite if V can be
divided into a partition of V1 and
V2, and each edge is in the form
of {a,b} where a is in V1 and b is
in V2.

▪▪ If every vertex in V1 is connected

to every vertex in V2, then we
have a complete bipartite graph.
This graph is denoted as Km,n,
where |V1|=m and |V2|=n.
 KURATOWSKI’S TWO GRAPHS: K5, K3,3
THEOREM 5-2: K3,3

Kuratowski’s second graph is also nonplanar.

Utilities Problem
 Properties of the two graphs of Kuratowski
1. Both are regular graphs.

2. Both are nonplanar.

3. Removal of one edge or a vertex makes each a

planar graph.

4. Kuratowski’s first graph is the nonplanar graph with

the smallest number of vertices, and Kuratowski’s
second graph is the nonplanar graph with the smallest
number of edges.

Thus both are the simplest nonplanar graphs.

 DIFFERENT REPRESENTATIONS OF A PLANAR GRAPH
THEOREM 5-3

Any simple planar graph can be embedded in a plane such that every
edge is drawn as a straight line segment.
 DIFFERENT REPRESENTATIONS OF A PLANAR GRAPH
Regions:

A plane representation of a graph divides the plane into regions (also

called windows, faces, or meshes), as shown in Fig. 11-55.

A region is characterized by the set of edges (or the set of vertices) of a

closed walk, forming its boundary.
 DIFFERENT REPRESENTATIONS OF A PLANAR GRAPH

Infinite Region:

• The portion of the plane lying outside a graph embedded

in a plane, such as region 4 (R4) in Fig. 11-55, is infinite in its
extent.

• Such a region is called the infinite, unbounded, outer, or

exterior region for that particular plane representation.

• Like other regions, the infinite region is also characterized

by a set of edges (or vertices) of a closed walk.
 DIFFERENT REPRESENTATIONS OF A PLANAR GRAPH
Infinite Region continued:

• By changing the embedding of a given planar graph, we can change the infinite region.

• For instance, Figs. 5-1(d) and 5-3 are two different embeddings of the same graph.

• The finite region v1 v3 v5 in Fig. 5-1(d) becomes the infinite region in Fig. 5-3.

• Theorem 5-6: A planar graph may be embedded in a plane such that any specified
region (i.e., specified by the edges forming it) can be made the infinite region.
 Euler’s Formula for number of regions
THEOREM 5-6

A connected planar graph with n vertices and e edges has e − n + 2 regions.

 Euler’s Formula for number of regions
COROLLARY

In any simple, connected planar graph with f regions, n vertices, and e edges

(e > 2), the following inequalities must hold :

Proof: Since each region is bounded by at least three edges and each edge

belongs to exactly two regions,

Substituting for f from Euler’s formula in inequality (5-5), Inequality,

 Euler’s formula to find if a graph is planar or not

• Finding whether K5 is planar or not, by using corollary of Euler’s formulart

• Applying corollary of Euler’s formula on K5

• Thus the graph violates inequality (5-6), and hence it is not planar.
 To prove the nonplanarity of Kuratowski’s second graph

• inequality (5-6) is only a necessary, but not a sufficient, condition for the
planarity of a graph.

• i.e., the mere satisfaction of this inequality does not guarantee the planarity
of a graph.

• For example, Kuratowski’s second graph, K3,3, satisfies (5-6), because

• e=9

• 3n − 6 = 3·6 − 6 = 12.

• Yet the graph is nonplanar.

 To prove the nonplanarity of Kuratowski’s second graph

• To prove the nonplanarity of Kuratowski’s second graph, we make use of the

additional fact that no region in this graph can be bounded with fewer than
four edges.

• Hence, if this graph were planar, we would have 2e ≥ 4f,

• and, substituting for f from Euler’s formula,

• 2e ≥ 4(e − n + 2),

• or 2·9 ≥ 4(9 − 6 + 2),

• or 18 ≥ 20, a contradiction.

• Hence the graph cannot be planar.

 DETECTION OF PLANARITY by Elementary Reduction
• Step 1: Consider only one component of G at a time for testing planarity.

• Step 2: Remove all self-loops, since addition or removal of self-loops does

not affect planarity.

• Step 3: Eliminate edges in parallel by removing all but one edge between
every pair of vertices, since parallel edges also do not affect planarity, .

• Step 4: Eliminate all edges in series, since elimination of a vertex of degree

two by merging two edges in series does not affect planarity.

• Repeated application of steps 3 and 4 until the graph is reduced:

1. A single edge, or

2. A complete graph of four vertices, or

3. A nonseparable, simple graph with n ≥ 5 and e ≥ 7.

DETECTION OF PLANARITY by Elementary Reduction : Example 1

Step 1
DETECTION OF PLANARITY by Elementary Reduction : Example 2
DETECTION OF PLANARITY by Elementary Reduction : Example 2

• In Theorem 5-8, all Hi falling in categories 1 or 2 are planar and need not be
checked further.
• The test can be applied easily to simple, connected, nonseparable graphs
of at least five vertices and with every vertex of degree three or more.
Next, we can check to see if e ≤ 3n − 6.
• If this inequality is not satisfied, the graph Hi is nonplanar.
• If the inequality is satisfied, we have to test the graph further using
homeomorphic graphs.
 Homeomorphic Graphs:
• Two graphs are said to be homeomorphic if one graph can be obtained
from the other by the creation of edges in series (i.e., by insertion of
vertices of degree two) or by the merger of edges in series.
• The three graphs in Fig. 5-8 are homeomorphic to each other, for instance.
• A graph G is planar if and only if every graph that is homeomorphic to G is
planar.

Fig. 5-8 Three graphs homeomorphic to each other.

 Homeomorphic Graphs:
THEOREM 5-9
A graph is nonplanar iff it contains a subgraph that is homeomorphic to either K5 or K3,3
 More Examples
▪▪ Ex 11.19 (b):
- Q3 is planar
- The complement of Q3 looks like nonplanar
- H is a subgraph of the complement of Q3, which shows
the complement of Q3 is nonplanar

29