Further Maths - Planarity Algorithm
Flashcards
2022-03-16
What is the first step of using the planarity algorithm to determine if a graph is planar?
Finding a Hamiltonian cycle.
After you’ve found a Hamiltonian cycle in the planarity algorithm, what do you do?
Draw the graph as a polygon.
You’ve got the Hamiltonian cycle as a polygon with edges not included in the Hamiltonian cycle as inside the polygon. What do you now write down to start determining if the graph is planar?
All the edges inside the polygon.
You’ve got the Hamiltonian cycle as a polygon with edges not included in the Hamiltonian cycle as inside the polygon. You’ve also got a list of the edges inside the polygon. What do you do at each step of the planarity algorithm?
- Look at an unlabelled edge and put an “I”
- Look for unlabelled edges crossing this edge and see if they cross each other
- If they do, the graph is not planar
- If they don’t, label these with an “O”
Why is it sometimes impossible to use the planarity algorithm?
There doesn’t exist a Hamiltonian cycle.
If there doesn’t exist a Hamiltonian cycle, and therefore the planarity algorithm can’t be used, does this necessarily mean that the graph is not planar?
No.