A graph is planar if it can be drawn in such a way that no arc crosses any other arc. There are algorithms for determining whether or not a graph is planar. The algorithm below can only be applied to graphs that have a Hamiltonian cycle (a cycle that passes through every vertex of the graph once and only once, and returns to its start vertex)
1. Identify a Hamiltonian cycle in the graph
2. Redraw the graph so that the Hamiltonian cycle forms a regular polygon and all edges are drawn as straight lines in the polygon
3. Choose any edge AB and decide this will stay inside the polygon
4. Consider any edges that cross AB
(a) if it is possible to move all these outside without producing crossings, go to step 5
(b) if it is not possible then the graph is non planar
5. Consider each remaining crossing inside and see if any edge may be moved outside to remove it, without creating a crossing inside
6. Stop when all crossings inside have been considered
(a) if there are no crossings inside or outside then the graph is planar
(b) if there is a crossing inside that cannot be removed then the graph is non-planar
Example: Applying the algorithm to the graph below
Results in the Hamiltonian path ABCD below
The edge BD can stay inside the polygon. AC can move outside the polygon and no arcs cross so the graph is planar.
The graph below is not planar. The arcs BE and BD can be moved outside the polygon but then the arc CE still crosses the arc AC and cannot be moved outside without crossing one of the newly outside arcs BE or BD.
