Planarity Testing

In the field of graph theory, Planarity Testing is a fundamental concept that deals with determining whether a given graph can be drawn on a plane without any edge crossings. Planarity testing plays an important role in various areas such as circuit design, computer graphics, and social network analysis. In this blog, we will discuss Planarity Testing, its properties, and how it is used in graph theory.

Planar Graph: A graph is called planar if it can be drawn on a plane without any edge crossing. For example, the following graph is planar.

Kuratowski’s Theorem: Kuratowski’s theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of either the complete graph K5 or the complete bipartite graph K3,3. A subdivision of a graph is obtained by inserting vertices into edges of the original graph. For example, the following graph is not planar because it contains a subdivision of K5.

Planarity Testing Algorithms: There are several algorithms to test whether a given graph is planar or not. One of the most common algorithms is the planarity testing algorithm based on the concept of a planar embedding. A planar embedding of a graph is a way of drawing the graph on a plane such that each vertex is represented by a distinct point, each edge is represented by a continuous curve connecting its endpoints, and no two curves intersect except at a common endpoint. The algorithm works by iteratively contracting edges of the graph until a planar embedding is obtained.

Properties of Planar Graph: Some important properties of planar graphs are:

1. The maximum number of edges in a planar graph with n vertices is 3n-6.
2. A planar graph is 4-colorable, i.e., its vertices can be colored with four colors such that no two adjacent vertices have the same color.
3. The dual of a planar graph is also planar.
4. The genus of a planar graph is zero. The genus of a graph is a measure of how many holes it has when drawn on a surface. For a planar graph, the surface is a plane, and hence it has zero genus.

Questions:

1. What is the definition of a planar graph?
2. How does the Kuratowski’s theorem help in planarity testing?
3. What is the time complexity of planarity testing algorithms?
4. Can a planar graph have multiple embeddings? If yes, explain.
5. What are the practical applications of planarity testing in real-world problems?

Conclusion: Planarity Testing is a fundamental concept in graph theory that deals with determining whether a given graph can be drawn on a plane without any edge crossings. The concept is widely used in various areas such as circuit design, computer graphics, and social network analysis. Kuratowski’s theorem provides a necessary and sufficient condition for a graph to be planar. Planarity testing algorithms based on planar embeddings are widely used to test the planarity of a graph. Planar graphs have several interesting properties, such as the maximum number of edges, 4-colorability, duality, and genus.

Acknowledgement
I would like to extend my sincere thanks to Dr. Rekha Sharma, Associate Professor, Department of Computer Engineering, Thakur College of Engineering and Technology, for the valuable guidance and support throughout the writing process of this blog on Planarity Testing. Their expertise and insights have been instrumental in shaping the content and ensuring its accuracy.

References
1) https://www.geeksforgeeks.org
2) https://www.javatpoint.com
3) https://www.wikipedia.org/
4) https://www.javatpoint.com
5) https://en.wikipedia.org/wiki/Graph_theory
6) https://www.coursera.org/learn/graphs
7) https://leetcode.com/study-plan/graph/