The planarity algorithm and Hamiltonian cycles
Studying this course? Keep your progress in one place.
Key facts
- A Hamiltonian cycle visits every vertex exactly once and returns to the start, using exactly edges.
- Eulerian uses every edge once; Hamiltonian visits every vertex once.
- The planarity algorithm draws a Hamiltonian cycle as a polygon, then places the other edges (chords) inside or outside.
- Chords conflict if their end points alternate around the cycle; chords sharing a vertex never conflict.
- Planar if every chord can be placed with conflicting chords on opposite sides; otherwise non-planar.
Hamiltonian cycles
A cycle through every vertex exactly once, returning to its start: it has exactly edges for vertices.
A Hamiltonian cycle passes through every vertex once and only once and returns to its start vertex. A graph with vertices needs a Hamiltonian cycle of exactly edges. A tree has no cycles, so it cannot have one.
To find one, write down the vertices of degree 2 first: both of their edges must be in the cycle. A route that does not return to the start is a Hamiltonian path, not a cycle.
Eulerian cycle
- Uses every edge once
- Vertices may repeat
Hamiltonian cycle
- Visits every vertex once
- Some edges may be unused
A graph has vertices. How many edges does a Hamiltonian cycle in it have?
The idea of the algorithm
Draw the Hamiltonian cycle as a loop; every other edge is a chord drawn inside or outside it.
A graph is planar if it can be drawn with no edges crossing. Trial and error can fail, so the planarity algorithm gives a systematic test for a graph that has a Hamiltonian cycle.
Draw the Hamiltonian cycle as a closed loop. Every other edge (a chord) joins two points on the loop, so it can be drawn inside or outside. The graph is planar exactly when the chords can be shared between inside and outside with no crossings on either side.
In the planarity algorithm, what is a chord?
The algorithm step by step
List the chords, find which conflict, then place conflicting chords on opposite sides.
Two chords conflict if their end points alternate around the cycle, so each separates the other's ends. Chords that share a vertex never conflict. To test chords and , check whether and lie on different arcs of the cycle between and .
Put one chord inside; any chord that conflicts with it goes outside. If some chord conflicts with chords on both sides, the graph is non-planar. List the conflicting pairs before placing anything.
- 1
Draw the cycle
find a Hamiltonian cycle and draw it as a polygon
- 2
List the chords
all edges not in the cycle
- 3
Find conflicts
chords whose end points alternate around the cycle
- 4
Place chords
put conflicting chords on opposite sides
- 5
Decide
all placed means planar; a chord with no valid side means non-planar
The cycle is . Do the chords and conflict?
A planar example
Every chord can be placed: conflicting chords go on opposite sides and the rest share sides.
A graph has Hamiltonian cycle and extra edges , , , . The only conflicts are with and with .
Inside the cycle
- 13
- 15
Outside the cycle
- 24
- 46
Worked example
Use the planarity algorithm to decide whether the graph is planar.
- 1
Conflicts: with (vertex is on one side of and on the other) and with . No other pairs conflict.
- 2
Place inside, so must go outside.
- 3
Place inside, so must go outside.
- 4
Inside, and share vertex . Outside, and share vertex . No crossings.
In this example, why can and both be drawn inside?
A non-planar example
A chord that conflicts with chords on both sides has no valid place, so the graph is non-planar.
Take with cycle and chords , , , , . You may choose any valid starting chord: the verdict is the same.
The six-vertex graph made from a hexagon with its three long diagonals is also non-planar by the same method: all three diagonals conflict with each other, and three mutually conflicting chords cannot be shared between two sides.
Worked example
Use the planarity algorithm on .
- 1
Conflicts: with and ; with and ; with .
- 2
Put inside. and conflict with , so both go outside.
- 3
conflicts with , so it goes inside.
- 4
conflicts with (inside) and (outside), so it has no valid side.
Why does the algorithm show that is non-planar?
Try an exam question
A graph has Hamiltonian cycle and three further edges , and . Use the planarity algorithm to show that the graph is not planar.
[4 marks]
- [1]The chords are , and .
- [1] conflicts with and with , and conflicts with .
- [1]Place inside, so and must both go outside.
- [1]But and conflict, so they cannot both be outside: the graph is not planar.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which of the following is a Hamiltonian cycle in this graph?
1 mark, marked against the mark scheme
Which of the following is a Hamiltonian cycle in this graph?
1 mark, marked against the mark scheme