Planarity Algorithm (Edexcel A Level Further Maths): Revision Note
Introduction to the Planarity Algorithm
What is the planarity algorithm?
A planar graph is one that can be drawn in a plane in such a way that no two edges connect except for at a vertex
You can determine whether or not a graph is planar by applying the planarity algorithm
The planarity algorithm can be applied to graphs that contain a Hamiltonian cycle
Identifying a Hamiltonian Cycle
What are Hamiltonian paths and cycles?
A Hamiltonian path is a path in which each vertex in a graph is visited exactly once
A Hamiltonian cycle is a cycle which visits each vertex in a graph exactly once and returns to its start vertex
If a graph contains a Hamiltonian cycle then it is known as a Hamiltonian graph
A graph is semi-Hamiltonian if it contains a Hamiltonian path but not a Hamiltonian cycle
The only way to show that a graph is Hamiltonian or semi-Hamiltonian is to identify a Hamiltonian cycle or Hamiltonian path
Examiner Tips and Tricks
If you are given an adjacency matrix and are asked to find a Hamiltonian cycle, make sure that you sketch out the graph first
Worked Example
Let G be the graph shown below.
Show that G is a Hamiltonian graph.
To show that the graph is Hamiltonian, identify a Hamiltonian cycle.
ABCFDEA
There is more than one possible correct Hamiltonian cycle in this graph
Applying the Planarity Algorithm
How is the planarity algorithm applied to a graph?
STEP 1 Draw a polygon (roughly regular) with the same number of vertices as the original graph
Identify a Hamiltonian cycle in the graph
Re-label the vertices in the order of the Hamiltonian cycle
STEP 2 Add all of the other edges in the original graph to the new graph inside the polygon
Make a list of all of these added edges
STEP 3 Choose an edge inside the polygon that has not yet been labelled and label it (I) (Inside)
If all edges (inside the polygon) now have a label, the graph is planar
STEP 4 Identify any edges inside the polygon that intersect the edge(s) that has just been labelled
If there are no such edges, return to STEP 3
If any of the edges that intersect the 'just labelled' edge also intersect each other, then the graph is non-planar
If the edges that intersect the 'just labelled' edge do not intersect with each other, give them each the opposite label to the 'just labelled' edge(s)
(I) and (O) (Outside) are opposite labels
If all edges (inside the polygon) now have a label, the graph is planar
If any edge (inside the polygon) remains unlabelled, return to the beginning of STEP 4
If the algorithm has determined that the graph is planar, then you can draw it with all of the edges labelled (I) on the inside of the polygon and all of the edges labelled (O) on the outside of the polygon
Examiner Tips and Tricks
Remember to draw your diagrams in pencil so that it's easy to erase any errors!
Worked Example
Show that the graph below is a planar graph by applying the planarity algorithm and draw it so that no two edges intersect.
STEP 1
There are 6 vertices so re-draw these 6 vertices connected with edges to form a hexagon
Find a Hamiltonian cycle in the original graph and label the vertices of the polygon in the order of the cycle
Hamiltonian cycle: ACBEDFA
STEP 2
Draw all of the remaining edges from the original graph on the inside of the polygon and make a list of these edges
Inside edges: AB, AE, AD, CE, EF
STEP 3
Label the first edge in that list, AB, (I)
Inside edges: AB (I), AE, AD, CE, EF
STEP 4
Edge CE is the only edge that intersects AB, so label it with the opposite label, (O)
Inside edges: AB (I), AE, AD, CE (O), EF
There are no other unlabelled edges that intersect with edge CE, so return to STEP 3
STEP 3
Choose the next unlabelled edge from the list of inside edges, AE, and label it (I)
Inside edges: AB (I), AE (I), AD, CE (O), EF
STEP 4
There are no unlabelled edges that intersect edge AE, so return to STEP 3STEP 3
Choose the next unlabelled edges from the list of inside edges, AD, and label it (I)
Inside edges: AB (I), AE (I), AD (I), CE (O), EF
STEP 4
Edge EF is the only edge that intersects AD, so label it with the opposite label, (O)
Inside edges: AB (I), AE (I), AD (I), CE (O), EF (O)
All edges are now labelled so the graph is planar
Re-draw the graph with edges labelled (I) inside the polygon and the edges labelled (O) outside the polygon
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?