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)
Responses