Planar Graphs

Planar Graphs-

 

A planar graph is a graph that can be drawn in a plane such that none of its edges cross each other.

 

Example-01:

 

 

This graph is an example of a planar graph.

 

Example-02:

 

 

Both the above graphs are equivalent and examples of planar graphs.

 

  • At first sight, first version of the graph may not seem to be planar because it has edges crossing each other.
  • But we can redraw the first version as shown in the second version which consists of no two edges crossing each other and therefore, both the graphs are planar.

 

Chromatic Number of Planar Graphs-

 

Chromatic number of planar graphs = Less than or equal to 4

 

Thus, any planar graph will require maximum 4 colors for coloring its vertices such that no two adjacent vertices have same colors.

 

Regions of the plane-

 

  • The planar representation of the graph splits the plane into connected areas called as regions of the plane.

 

Degree of the Regions-

 

Each region has some degree associated with it given as-

  • Degree of an interior region = Number of edges enclosing that region
  • Degree of an exterior region = Number of edges exposed to that region

 

NOTE

In a simple planar graph, degree of each region is at least 3 (>=3)

 

Example-

 

The following planar graph splits the plane into 4 regions-

 

 

In this graph-

  • Degree (R1) = 3
  • Degree (R2) = 3
  • Degree (R3) = 3
  • Degree (R4) = 5

 

Properties of Planar Graphs-

 

Property-01:

 

In any planar graph,

Sum of degrees of all the vertices = 2 x Total number of edges in the graph

 

 

Property-02:

 

In any planar graph,

Sum of degrees of all the regions = 2 x Total number of edges in the graph

 

 

Special Cases-

 

Case-01:

 

In any planar graph, if degree of each region is K, then-

 

K x |R| = 2 x |E|

 

Case-02:

 

In any planar graph, if degree of each region is at least K (>=K), then-

 

K x |R| <= 2 x |E|

 

Case-03:

 

In any planar graph, if degree of each region is at most K (<=K), then-

 

K x |R| >= 2 x |E|

 

Property-03: Euler’s Formula

 

If G is a connected planar simple graph with ‘e’ edges, ‘v’ vertices and ‘r’ number of regions in the planar representation of G, then-

 

r = e – v + 2

 

The formula remains same in all the planar representations of the graph.

 

Property-04:

 

If G is a planar graph with k components, then-

 

r = e – v + (k + 1)

 

PRACTICE PROBLEMS BASED ON PLANAR GRAPHS-

 

Problem-01:

Let G be a connected planar simple graph with 25 vertices and 60 edges. Find the number of regions in G.

 

Solution-

 

By Euler’s formula, we know-

r = e – v + 2

We have, v = 25 and e = 60. Substituting the values, we get-

 r = 60 – 25 + 2

∴ r = 37

Thus, Total number of regions in G = 37

 

Problem-02:

Let G be a planar graph with 10 vertices, 3 components and 9 edges. Find the number of regions in G.

 

Solution-

 

By Euler’s formula, we know-

r = e – v + (k+1)

We have, v = 10, e = 9 and k = 3. Substituting the values, we get-

 r = 9 – 10 + (3+1)

∴ r = 3

Thus, Total number of regions in G = 3

 

Problem-03:

Let G be a connected planar simple graph with 20 vertices and degree of each vertex is 3. Find the number of regions in G.

 

Solution-

 

Step-01: Calculation of total number of edges in G-

 

By sum of degrees of vertices theorem, we know-

Sum of degrees of all the vertices = 2 x Total number of edges

 

We have, v = 20 and degree of each vertex = 3. Substituting the values, we get-

 20 x 3 = 2 x |E|

∴ |E| = 30

Thus, Total number of edges in G = 30

 

Step-02: Calculation of total number of regions in G-

 

Now, By Euler’s formula, we know-

r = e – v + 2

We have, v = 20 and e = 30. Substituting the values, we get-

r = 30 – 20 + 2

∴ r = 12

Thus, Total number of regions in G = 12

 

Problem-04:

Let G be a connected planar simple graph with 35 regions, degree of each region is 6. Find the number of vertices in G.

 

Solution-

 

Step-01: Calculation of total number of edges in G-

 

By sum of degrees of regions theorem, we know-

Sum of degrees of all the regions = 2 x Total number of edges

 

We have, r = 35 and degree of each region = 6. Substituting the values, we get-

 35 x 6 = 2 x |E|

∴ |E| = 105

Thus, Total number of edges in G = 105

 

Step-02: Calculation of total number of vertices in G-

 

Now, By Euler’s formula, we know-

r = e – v + 2

We have, r = 35 and e = 105. Substituting the values, we get-

35 = 105 – v + 2

∴ v = 72

Thus, Total number of vertices in G = 72

 

Problem-05:

Let G be a connected planar graph with 12 vertices, 30 edges and degree of each region is K. Find the value of K.

 

Solution-

 

Step-01: Calculation of total number of regions in G-

 

By Euler’s formula, we know-

r = e – v + 2

We have, v = 12 and e = 30. Substituting the values, we get-

r = 30 – 12 + 2

∴ r = 20

 

Step-02: Calculation of value of k-

 

Now, By sum of degrees of regions theorem, we know-

Sum of degrees of all the regions = 2 x Total number of edges

So, we have-

20 x k = 2 x 30

∴ k = 3

Thus, Degree of each region in G = 3

 

Problem-06:

What is the maximum number of regions possible in a simple planar graph with 10 edges?

 

Solution-

 

We know, In a simple planar graph, degree of each region is >= 3

So, we have-

3 x |R| <= 2 x |E|

 

We have, |E| = 10. Substituting the value, we get-

3 x |R| <= 2 x 10

|R| <= 6.67

|R| <= 6

Thus, Maximum number of regions in G = 6

 

Problem-07:

What is the minimum number of edges necessary in a simple planar graph with 15 regions?

 

Solution-

 

We know, In a simple planar graph, degree of each region is >= 3

So, we have-

3 x |R| <= 2 x |E|

 

We have, |R| = 15. Substituting the value, we get-

3 x 15 <= 2 x |E|

|E| >= 22.5

|E| >= 23

Thus, Minimum number of edges required in G = 23

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Planar Graphs
Article Name
Planar Graphs
Description
A planar graph is a graph that can be drawn in a plane such that none of its edges cross each other. Properties of Planar Graphs and Numerical Problems on Planar Graphs.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-