A LevelFurther Maths: Decision Maths 1EdexcelRevision NotesAlgorithms & Graph TheoryGraphsPlanarity Algorithm

Planarity Algorithm (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Test Yourself
Naomi C

Author

Naomi C

Expertise

Maths

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

Exam Tip

  • 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.

3-10-5-ib-ai-hl-travelling-salesman-problem-we-1

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

Exam Tip

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.

planarity-algorithm---original-graph

  • 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

w7App0FS_planarity-algorithm---step-1

  • 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

ixkyembi_planarity-algorithm---step-2

Inside edges: AB, AE, AD, CE, EF

  • STEP 3
    Label the first edge in that list, AB, (I)

o9uLcZSJ_planarity-algorithm---step-3

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)

phQec7sF_planarity-algorithm---step-4a

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)

BSsPw7eB_planarity-algorithm---step-4b

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 3
     
  • STEP 3
    Choose the next unlabelled edges from the list of inside edges, AD, and label it (I)

iaOQPJ8y_planarity-algorithm---step-4c

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)

f0kt~68Q_planarity-algorithm---step-4d

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

0S9Vd6Ga_planarity-algorithm---final-graph

You've read 0 of your 0 free revision notes

Get unlimited access

to absolutely everything:

  • Downloadable PDFs
  • Unlimited Revision Notes
  • Topic Questions
  • Past Papers
  • Model Answers
  • Videos (Maths and Science)

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Test yourselfNext topic

    Did this page help you?

    Naomi C

    Author: Naomi C

    Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.