Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Planar Graph
2.1.
Regions of a Graph
2.1.1.
Finite Region
2.1.2.
Infinite Region
2.2.
Properties of Planar Graphs
3.
Non-Planar Graph
3.1.
Properties of Non-Planar Graph
4.
Graph Coloring
4.1.
Proper Coloring
4.2.
Applications of Graph Coloring
4.3.
Handshaking Algorithm
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Planar and Non-Planar Graphs

Author Naman Kukreja
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The one thing we all see all around us is data, data surrounds us, and sometimes understanding data is crucial. There are many ways to represent the data. We can represent the data in text or virtual representation. So, where is the need for a graph?

Graphs are the textual representation of data with significantly less space required and can represent small data efficiently so that everyone can understand it.

The graph contains vertices as the nodes, and edges are the lines connecting different vertices representing the data. The graph also has different types to represent data: planar and non-planar graphs.

We will learn more about planar and non-planar graphs while moving further with the blog, so let's move on with our topic without wasting any time.

Planar Graph

It is the type of graph that can be drawn in a plane with no edge overlap or cross each other.

Example:

Here we will discuss the example of a planar graph with four vertices.

And can also connect like this:

Here first, we connected internally then externally.

Regions of a Graph

To understand the region in a graph, assume a graph G = (V, E) where V is the number of vertices and E is the number of edges present in the graph. A region is defined as the area of the plane in the graph which is enclosed or surrounded by edges and can not be subdivided further.

A planar graph divides the graph into one or more regions, one of which is an infinite region. Finite and infinite areas are explained below:

Finite Region

If the area of the region in the graph or any plane is finite, then it is known as finite region.

The planar graph can have more than one finite region.

Infinite Region

If the area of the region in the graph or any plane is infinite, then it is known as infinite region. The planar graph has only one infinite region.

Example

Consider the graph given below. Find the name and number of finite and infinite regions.

Solution:

There are five regions present in the above graph r1, r2, r3, r4, r5.

Among the above five regions, r2, r3, r4, r5 are the finite region.

Whereas r1 is the infinite region.

Properties of Planar Graphs

There are some properties of a planar graph. We will list all of them below:

  • If a connected planar graph G has r regions and e edges, then r ≤Planar and Non-Planar Graphse.
  • If a connected planar graph G has v vertices, r regions, and e edges, then v-e+r=2.
  • If a connected planar graph G has v vertices and e edges, then 3v-e>=6.
  • A complete graph Kn is said to be planar if and only if n<5.
  • A complete bipartite graph Kmn is said to be planar if and only if n>3 or m<3.

Example

Consider the graph given below and prove that it is planar.

In the above graph, there are four vertices and six edges. So 3v-e = 3*4-6=6, which holds the property three hence it is a planar graph.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Non-Planar Graph

A graph is known as non-planar when it can only be drawn on a plane with edges overlapping or crossing.

Example: 

We have a non-planar graph with overlapping edges in the example given below.

Properties of Non-Planar Graph

A graph with a subgraph homeomorphic to K5 or K3,3  is known as a non-planar graph.

Example 1:

Consider the graph given above and prove that it is non-planar.

Solution:

The above graph has five vertices and ten edges hence 3*v -e = 3*5 -10 =5. therefore it does not follow the third property hence it is a non-planar graph.

Example 2:

Prove that the graph below is non-planar by finding a homeomorphic subgraph to K5 or K3,3.

Solution: We will try to remove some edges to achieve a homeomorphic subgraph to K5 or K3,3. We can accomplish this by eliminating the edges (V3, V4), (V5, V4), (V1, V4). The graph after removing the following edges will look like this:

Graph Coloring

Assume that G=(V, E) is a graph with no more than two edges. A vertex coloring of G is a color assigned to G's vertices that result in adjacent vertices having distinct hues. If there is a coloring of G that employs M-Colors, then G is M-Colorable.

Proper Coloring

Coloring is said to be proper if any two adjacent vertices v and u have different colors. Otherwise, it is known as improper coloring.

Example: 

Given a graph below, color it properly using different colors.

Solution:

The graph colored properly with four colors will look like this:

The graph properly colored by using three colors will look like this:

Chromatic number of a Graph

It refers to the minimum number of colors required to color the graph properly.

Applications of Graph Coloring

There are many applications of graph coloring. We will discuss some of them here.

  • Map Coloring
  • Register Allocation
  • Making a Timetable
  • MRFA(Mobile Radio Frequency Assignment)
  • Bipartite Graph Checking

Handshaking Algorithm

It states that the sum of degrees of all the vertices of a Graph G equals twice the number of edges in the same graph.

Mathematically it can be stated as:

              ∑v∈Vdeg(v)=2e

FAQs

1. What do you mean by the Planar graph?
A graph that can be drawn on a plane with any overlapping edges is known as a planar graph.
 

2. Write some applications of graph coloring.
It is used for map coloring, used for checking bipartite graphs, etc.
 

3. How many infinite regions can a planar graph have?
The planar graph has only one infinite region.
 

4. What is the condition of a complete graph to be said planar?
A complete graph Kn is said to be planar if and only if n<5.

Key Takeaways

In this article, we have extensively discussed the planar and non-planar graphs along with their examples and properties. We have also discussed graph coloring with its examples.

We hope that this blog has helped you enhance your knowledge regarding graphs and if you would like to learn more, check out our articles on Code studio. Do upvote our blog to help other ninjas grow.

 “Happy Coding!”

Previous article
What is Undirected Graph?
Next article
Matching in Graph Theory
Live masterclass