Tag: Planar Graph

Types of Graphs in Graph Theory

Graphs-

 

  • A graph is a collection of vertices connected to each other through a set of edges.
  • The study of graphs is known as Graph Theory.

 

Formal Definition

Formally,

A graph is defined as an ordered pair of a set of vertices and a set of edges.

G = (V, E)

Here, V is the set of vertices and E is the set of edges connecting the vertices.

 

Example-

 

 

In this graph,

V = { A , B , C , D , E }

E = { AB , AC , BD , CD , DE }

 

Types of Graphs-

 

Various important types of graphs in graph theory are-

 

 

  1. Null Graph
  2. Trivial Graph
  3. Non-directed Graph
  4. Directed Graph
  5. Connected Graph
  6. Disconnected Graph
  7. Regular Graph
  8. Complete Graph
  9. Cycle Graph
  10. Cyclic Graph
  11. Acyclic Graph
  12. Finite Graph
  13. Infinite Graph
  14. Bipartite Graph
  15. Planar Graph
  16. Simple Graph
  17. Multi Graph
  18. Pseudo Graph
  19. Euler Graph
  20. Hamiltonian Graph

 

1. Null Graph-

 

  • A graph whose edge set is empty is called as a null graph.
  • In  other words, a null graph does not contain any edges in it.

 

Example-

 

 

Here,

  • This graph consists only of the vertices and there are no edges in it.
  • Since the edge set is empty, therefore it is a null graph.

 

2. Trivial Graph-

 

  • A graph having only one vertex in it is called as a trivial graph.
  • It is the smallest possible graph.

 

Example-

 

 

Here,

  • This graph consists of only one vertex and there are no edges in it.
  • Since only one vertex is present, therefore it is a trivial graph.

 

3. Non-Directed Graph-

 

  • A graph in which all the edges are undirected is called as a non-directed graph.
  • In other words, edges of an undirected graph do not contain any direction.

 

Example-

 

 

Here,

  • This graph consists of four vertices and four undirected edges.
  • Since all the edges are undirected, therefore it is a non-directed graph.

 

4. Directed Graph-

 

  • A graph in which all the edges are directed is called as a directed graph.
  • In other words, all the edges of a directed graph contain some direction.
  • Directed graphs are also called as digraphs.

 

Example-

 

 

Here,

  • This graph consists of four vertices and four directed edges.
  • Since all the edges are directed, therefore it is a directed graph.

 

5. Connected Graph-

 

  • A graph in which we can visit from any one vertex to any other vertex is called as a connected graph.
  • In connected graph, at least one path exists between every pair of vertices.

 

Example-

 

 

Here,

  • In this graph, we can visit from any one vertex to any other vertex.
  • There exists at least one path between every pair of vertices.
  • Therefore, it is a connected graph.

 

6. Disconnected Graph-

 

  • A graph in which there does not exist any path between at least one pair of vertices is called as a disconnected graph.

 

Example-

 

 

Here,

  • This graph consists of two independent components which are disconnected.
  • It is not possible to visit from the vertices of one component to the vertices of other component.
  • Therefore, it is a disconnected graph.

 

7. Regular Graph-

 

  • A graph in which degree of all the vertices is same is called as a regular graph.
  • If all the vertices in a graph are of degree ‘k’, then it is called as a “k-regular graph“.

 

Examples-

 

 

In these graphs,

  • All the vertices have degree-2.
  • Therefore, they are 2-Regular graphs.

 

8. Complete Graph-

 

  • A graph in which exactly one edge is present between every pair of vertices is called as a complete graph.
  • A complete graph of ‘n’ vertices contains exactly nC2 edges.
  • A complete graph of ‘n’ vertices is represented as Kn.

 

Examples-

 

 

In these graphs,

  • Each vertex is connected with all the remaining vertices through exactly one edge.
  • Therefore, they are complete graphs.

 

9. Cycle Graph-

 

  • A simple graph of ‘n’ vertices (n>=3) and n edges forming a cycle of length ‘n’ is called as a cycle graph.
  • In a cycle graph, all the vertices are of degree 2.

 

Examples-

 

 

In these graphs,

  • Each vertex is having degree 2.
  • Therefore, they are cycle graphs.

 

10. Cyclic Graph-

 

  • A graph containing at least one cycle in it is called as a cyclic graph.

 

Example-

 

 

Here,

  • This graph contains two cycles in it.
  • Therefore, it is a cyclic graph.

 

11. Acyclic Graph-

 

  • A graph not containing any cycle in it is called as an acyclic graph.

 

Example-

 

 

Here,

  • This graph do not contain any cycle in it.
  • Therefore, it is an acyclic graph.

 

12. Finite Graph-

 

  • A graph consisting of finite number of vertices and edges is called as a finite graph.

 

Example-

 

 

Here,

  • This graph consists of finite number of vertices and edges.
  • Therefore, it is a finite graph.

 

13. Infinite Graph-

 

  • A graph consisting of infinite number of vertices and edges is called as an infinite graph.

 

Example-

 

 

Here,

  • This graph consists of infinite number of vertices and edges.
  • Therefore, it is an infinite graph.

 

14. Bipartite Graph-

 

A bipartite graph is a graph where-

  • Vertices can be divided into two sets X and Y.
  • The vertices of set X only join with the vertices of set Y.
  • None of the vertices belonging to the same set join each other.

 

Example-

 

 

Read More- Bipartite Graphs

 

15. Planar Graph-

 

  • A planar graph is a graph that we can draw in a plane such that no two edges of it cross each other.

 

Example-

 

 

Here,

  • This graph can be drawn in a plane without crossing any edges.
  • Therefore, it is a planar graph.

 

Read More- Planar Graphs

 

16. Simple Graph-

 

  • A graph having no self loops and no parallel edges in it is called as a simple graph.

 

Example-

 

 

Here,

  • This graph consists of three vertices and three edges.
  • There are neither self loops nor parallel edges.
  • Therefore, it is a simple graph.

 

17. Multi Graph-

 

  • A graph having no self loops but having parallel edge(s) in it is called as a multi graph.

 

Example-

 

 

Here,

  • This graph consists of three vertices and four edges out of which one edge is a parallel edge.
  • There are no self loops but a parallel edge is present.
  • Therefore, it is a multi graph.

 

18. Pseudo Graph-

 

  • A graph having no parallel edges but having self loop(s) in it is called as a pseudo graph.

 

Example-

 

 

Here,

  • This graph consists of three vertices and four edges out of which one edge is a self loop.
  • There are no parallel edges but a self loop is present.
  • Therefore, it is a pseudo graph.

 

19. Euler Graph-

 

  • Euler Graph is a connected graph in which all the vertices are even degree.

 

Example-

 

 

Here,

  • This graph is a connected graph.
  • The degree of all the vertices is even.
  • Therefore, it is an Euler graph.

 

Read More- Euler Graphs

 

20. Hamiltonian Graph-

 

  • If there exists a closed walk in the connected graph that visits every vertex of the graph exactly once (except starting vertex) without repeating the edges, then such a graph is called as a Hamiltonian graph.

 

Example-

 

 

Here,

  • This graph contains a closed walk ABCDEFG that visits all the vertices (except starting vertex) exactly once.
  • All the vertices are visited without repeating the edges.
  • Therefore, it is a Hamiltonian Graph.

 

Read More- Hamiltonian Graphs

 

Important Points-

 

  • Edge set of a graph can be empty but vertex set of a graph can not be empty.
  • Every polygon is a 2-Regular Graph.
  • Every complete graph of ‘n’ vertices is a (n-1)-regular graph.
  • Every regular graph need not be a complete graph.

 

Remember-

 

The following table is useful to remember different types of graphs-

 

Self-Loop(s)Parallel Edge(s)
GraphYesYes
Simple GraphNoNo
Multi GraphNoYes
Pseudo GraphYesNo

 

Applications of Graph Theory-

 

Graph theory has its applications in diverse fields of engineering-

 

1. Electrical Engineering-

 

  • The concepts of graph theory are used extensively in designing circuit connections.
  • The types or organization of connections are named as topologies.
  • Some examples for topologies are star, bridge, series and parallel topologies.

 

2. Computer Science-

 

Graph theory is used for the study of algorithms such as-

 

3. Computer Network-

 

The relationships among interconnected computers in the network follows the principles of graph theory.

 

4. Science-

 

Following structures are represented by graphs-

  • Molecular structure of a substance
  • Chemical structure of a substance
  • DNA structure of an organism etc

 

5. Linguistics-

 

The parsing tree of a language and grammar of a language uses graphs.

 

6. Other Applications-

 

  • Routes between the cities are represented using graphs.
  • Hierarchical ordered information such as family tree are represented using special types of graphs called trees.

 

Next Article- Planar Graph

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Planar Graph in Graph Theory | Planar Graph Example

Types of Graphs-

 

Before you go through this article, make sure that you have gone through the previous article on various Types of Graphs in Graph Theory.

 

We have discussed-

  • A graph is a collection of vertices connected to each other through a set of edges.
  • The study of graphs is known as Graph Theory.

 

 

In this article, we will discuss about Planar Graphs.

 

Planar Graph-

 

A planar graph may be defined as-

 

In graph theory,

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

 

Planar Graph Example-

 

The following graph is an example of a planar graph-

 

 

Here,

  • In this graph, no two edges cross each other.
  • Therefore, it is a planar graph.

 

Regions of Plane-

 

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

 

Each region has some degree associated with it given as-

  • Degree of Interior region = Number of edges enclosing that region
  • Degree of Exterior region = Number of edges exposed to that region

 

Example-

 

Consider the following planar graph-

 

 

Here, this planar graph splits the plane into 4 regions- R1, R2, R3 and R4 where-

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

 

Planar Graph Chromatic Number-

 

  • Chromatic Number of any planar graph is always less than or equal to 4.
  • Thus, any planar graph always requires maximum 4 colors for coloring its vertices.

 

Planar Graph Properties-

 

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:

 

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

 

This is known as Euler’s Formula.

It 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)

 

Also Read- Bipartite Graph

 

PRACTICE PROBLEMS BASED ON PLANAR GRAPH IN GRAPH THEORY-

 

Problem-01:

 

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

 

Solution-

 

Given-

  • Number of vertices (v) = 25
  • Number of edges (e) = 60

 

By Euler’s formula, we know r = e – v + 2.

 

Substituting the values, we get-

Number of regions (r)

= 60 – 25 + 2

= 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-

 

Given-

  • Number of vertices (v) = 10
  • Number of edges (e) = 9
  • Number of components (k) = 3

 

By Euler’s formula, we know r = e – v + (k+1).

 

Substituting the values, we get-

Number of regions (r)

= 9 – 10 + (3+1)

= -1 + 4

= 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-

 

Given-

  • Number of vertices (v) = 20
  • Degree of each vertex (d) = 3

 

Calculating Total Number Of Edges (e)-

 

By sum of degrees of vertices theorem, we have-

 

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

Number of vertices x Degree of each vertex = 2 x Total number of edges

20 x 3 = 2 x e

∴ e = 30

 

Thus, Total number of edges in G = 30.

 

Calculating Total Number Of Regions (r)-

 

By Euler’s formula, we know r = e – v + 2.

 

Substituting the values, we get-

Number of regions (r)

= 30 – 20 + 2

= 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-

 

Given-

  • Number of regions (n) = 35
  • Degree of each region (d) = 6

 

Calculating Total Number Of Edges (e)-

 

By sum of degrees of regions theorem, we have-

 

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

Number of regions x Degree of each region = 2 x Total number of edges

35 x 6 = 2 x e

∴ e = 105

 

Thus, Total number of edges in G = 105.

 

Calculating Total Number Of Vertices (v)-

 

By Euler’s formula, we know r = e – v + 2.

 

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-

 

Given-

  • Number of vertices (v) = 12
  • Number of edges (e) = 30
  • Degree of each region (d) = k

 

Calculating Total Number Of Regions (r)-

 

By Euler’s formula, we know r = e – v + 2.

 

Substituting the values, we get-

Number of regions (r)

= 30 – 12 + 2

= 20

 

Thus, Total number of regions in G = 20.

 

Calculating Value Of k-

 

By sum of degrees of regions theorem, we have-

 

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

Number of regions x Degree of each region = 2 x Total number of edges

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-

 

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

So, we have 3 x |R| <= 2 x |E|.

 

Substituting the value |E| = 10, 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-

 

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

So, we have 3 x |R| <= 2 x |E|.

 

Substituting the value |R| = 15, we get-

3 x 15 <= 2 x |E|

|E| >= 22.5

|E| >= 23

 

Thus, Minimum number of edges required in G = 23.

 

To gain better understanding about Planar Graphs in Graph Theory,

Watch this Video Lecture

 

Next Article- Euler Graph

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.