The Planarity Algorithm

Basic Principles

Planarity involves determining whether a graph can be drawn in such a way that no edges cross each other. This is important in a variety of practical applications, such as circuit design.
The planarity algorithm enables us to systematically test whether a given graph is planar.

Kuratowski’s Theorem is a pivotal part of the planarity algorithm. According to this theorem, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 (complete graph on five vertices) or K3,3 (complete bipartite graph on six vertices, with each partition containing three vertices).
When applying the algorithm to a graph, you repeatedly search for and remove vertices of degree less than 5. If this process leaves you with an empty set (the trivial graph), the original graph is planar.

The Wagner’s Theorem is an essential concept related to the Planarity Algorithm. It states that a finite graph is planar if and only if it does not contain a minor of the graphs K5 or K3,3.
Certain special cases like the utility graph and the Peterson graph are also relevant when studying the planarity algorithm. Both graphs are commonly used as examples of non-planar graphs.

Understanding how to manually test for planarity by drawing is a crucial skill. You should be able to redraw the graphs in different ways to test for edge-crossings.
One effective strategy for testing planarity manually is to use the circle method, where you arrange vertices on a circle and attempt to draw internal edges without them intersecting.

Remember, practising with different graphs and diagram types will be helpful to master these concepts.