D1 1.4 - The planarity algorithm | Edexcel A-Level Further Mathematics

You will recognise Hamiltonian cycles and apply the planarity algorithm by assigning the remaining arcs to two lists. You will justify both a successful assignment and a contradiction.

A cycle through every node

A square with both diagonals has a crossing. Does that prove $K_4$ is not planar? No: move one node inside a triangle and the very same six connections can be drawn without crossings. The real question is whether a crossing-free drawing is possible at all.

You already know

A planar graph can be drawn with no arc meeting another except at a common endpoint. Moving nodes and bending arcs preserve the graph's connections. A cycle returns to its start with no other repeated node.

The left drawing looks troublesome; the right drawing proves that the graph is planar. An unmarked crossing in the left drawing is not an extra node.

[DIAGRAM: asset_name: 9fm0-d1-165-k4-redrawing.png; asset_slug: 9fm0-d1-165-k4-redrawing; caption: Two drawings of K4: a crossing in one drawing does not prevent planarity.; description: A square ABCD with both diagonals on the left, and the same complete graph drawn as triangle ABC with D inside on the right; every pair is joined and only the left drawing has a crossing.]

Hamiltonian cycle

A Hamiltonian cycle is a cycle that visits every node of a graph exactly once before returning to its start.

For example, $A,B,C,D,A$ is a Hamiltonian cycle in either drawing of $K_4$ . It uses four of the six arcs. The restriction concerns nodes, whereas an Eulerian circuit uses every arc once and may revisit nodes.

The planarity algorithm here starts with a Hamiltonian cycle, often supplied in the question. Redraw its nodes around a circle in the cycle's order. The cycle forms the boundary; every other arc must then be drawn inside or outside it. Some planar graphs, such as trees with more than one node, have no Hamiltonian cycle: failing to find such a cycle is not evidence of non-planarity.

Key idea

A Hamiltonian cycle visits every node once and returns. It does not have to use every arc, and a crossing in one drawing does not prove a graph is non-planar.

Check the start-and-finish condition as carefully as the list of visited nodes.

Assigning arcs to two lists

Once a Hamiltonian cycle is on a circle, draw the remaining arcs as chords to see which pairs would cross. A pair that crosses cannot both stay inside; neither can both go outside. The two arcs must be assigned to opposite sides.

Two chords with four different endpoints cross precisely when their endpoints alternate around the cycle. On the cycle $A,B,C,D,E,F,A$ , the endpoints of $AC$ and $BD$ occur as $A,B,C,D$ , so they alternate. The chords $AC$ and $CE$ share $C$ , so they do not conflict.

Two-list planarity algorithm

Put a Hamiltonian cycle around a circle. List all arcs not on the cycle.
Choose one remaining arc and put it in List I. Put every arc crossing it in List II.
Continue the forced assignments: arcs crossing an arc in one list must go in the other list.
If unassigned arcs remain with no forced assignment, start one in either list and continue. Include every remaining arc.
If all arcs are assigned with no crossings within either list, the graph is planar: draw List I inside and List II outside. If the assignments force an arc into both lists, the graph is non-planar.

The labels I and II can be interchanged. What matters is that every non-cycle arc is accounted for and every crossing pair is separated. A circle's inside and outside obey the same obstruction: two pairs of alternating endpoints cannot be joined on the same side without crossing. This explains both the forced placements and a contradiction.

Not in the formula booklet: learn it.

[DIAGRAM: asset_name: 9fm0-d1-165-two-list-redrawing.png; asset_slug: 9fm0-d1-165-two-list-redrawing; caption: Crossing pairs are separated by keeping List I inside and routing List II outside the Hamiltonian cycle.; description: Two circular drawings with cycle ABCDEFA and chords AC, BD, CE, DF; left all chords are inside with crossings, right AC and CE remain inside while BD and DF curve outside without crossings; list colours and contents are labelled.]
Crossing pairs are separated by keeping List I inside and routing List II outside the Hamiltonian cycle.

Worked example 1: propagating the assignments

Question. A graph has Hamiltonian cycle $A,B,C,D,E,F,A$ and additional arcs $AC,BD,CE,DF$ . Use the planarity algorithm to decide whether it is planar.

Plan. Identify crossing pairs in the circular order, then force each crossing pair into opposite lists.

The crossing pairs are $AC$ with $BD$ , $BD$ with $CE$ , and $CE$ with $DF$ . Start with $AC$ in List I.

Step	List I	List II	Reason
$1$	$AC$	—	Choose a starting arc
$2$	$AC$	$BD$	$BD$ crosses $AC$
$3$	$AC,CE$	$BD$	$CE$ crosses $BD$
$4$	$AC,CE$	$BD,DF$	$DF$ crosses $CE$

Why can $AC$ and $CE$ share a list? They meet only at their common endpoint $C$ , which is permitted.

Answer. The graph is planar. All four additional arcs are assigned; neither list contains a crossing pair, and no arc is forced into both lists.

Check. The right-hand drawing places $AC,CE$ inside and $BD,DF$ outside without crossings.

Worked example 2 adds only the arc $AE$ . Its conflicts decide which list can accept it.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 1.4 - The planarity algorithm

A cycle through every node

Assigning arcs to two lists

Continue this lesson.

Learn faster with Nova