Planar and Non-Planar Graphs

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 K₅ or K_3,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 K₅ or K_3,3.

Solution: We will try to remove some edges to achieve a homeomorphic subgraph to K₅ or K_3,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 K_n 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!”