The Planarity Algorithm
The Planarity Algorithm
Method
- Identify a Hamiltonian Cycle
- Arrange it in a polygon (E.G. 8 nodes in a hamiltonian cycle would be drawn as an octogon)
- Draw arcs inside the polygon created to match the original graph before the hamiltonian cycle
- Make a list of all the arcs inside the polygon (E.G. AC, DF, CG)
- Choose any unlabeled arc in the list and label it (I). If all arcs are now labeled, then the graph is planar
- Look at the unlabeled arcs that cross over the arc that was just labelled
- If there are none, go to step 5
- If any of these arcs cross over each other, then the graph is non-planar
- If none of these arcs cross each other, give the (O) tag to the arc that was previously labelled (I)
- If all edges are now labelled, the graph is planar, otherwise go back to the beginning of step 6.