D1.1.4 The planarity algorithm for planar graphs.

Section
D1.1 Algorithms and graph theory
Level
A level only
Statement
The planarity algorithm for planar graphs.
Guidance
Students will be expected to be familiar with the term ‘Hamiltonian cycle’.
Since 2018
4 parts, 6 marks · topic pages: Algorithms, sorting, bin packing and graph theory

Back to the checklist

June 2023 · Paper 3D (Decision 1) · Q1(b) 1 mark
(b) Write down an example of a Hamiltonian cycle on G. (1)
June 2023 · Paper 3D (Decision 1) · Q1(c) 1 mark
(c) State whether or not G is planar, justifying your answer. (1)
Nov 2021 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. A U B V C W X E Y Figure 1 A Hamiltonian cycle for the graph in Figure 1 begins C, V, E, X, A, W, …. (a) Complete the Hamiltonian cycle. (1)
Nov 2021 · Paper 3D (Decision 1) · Q1(b) 3 marks
(b) Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer. (3)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.