10.2.3 Planarity Algorithm

Introduction to Planarity

A graph is planar if it can be drawn on a plane without any edges crossing. The planarity algorithm determines whether a graph is planar and provides steps to convert non-planar graphs into planar ones by redrawing or modifying edges.

Planarity is essential in graph theory for applications such as network design, circuit layouts, and topology.

Hamiltonian Cycle

A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once and returns to the starting vertex. A graph with a Hamiltonian cycle is called Hamiltonian.

infoNote

Example:

For a square with a diagonal :

ABCDA

\text{Cycle: } A \to B \to C \to D \to A

Kuratowski's Theorem

A graph is non-planar if and only if it contains a subgraph homeomorphic to $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite graph).

Planarity Algorithm Steps

Identify Edges and Vertices: Start by listing all vertices and edges in the graph.
Check for $K_5$ or $K_{3,3}$ :

Subgraphs homeomorphic to $K_5$ or $K_{3,3}$ indicate non-planarity.
$K_5$ : Complete graph with 5 vertices and 10 edges.
$K_{3,3}$ : Bipartite graph with two sets of 3 vertices, each connected to all vertices in the other set.

Apply Euler's Formula (Planar Graphs): For a connected planar graph:

v - e + f = 2

where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces (including the outer face).

Rearrange Edges to Avoid Crossings: Attempt to redraw the graph without any overlapping edges.

Worked Examples

infoNote

Example 1: Checking Planarity of a Graph

Problem:

Determine if the following graph is planar:

Vertices: $A, B, C, D, E$
Edges: $AB, BC, CD, DA, AC, BD$

Step 1: Count Vertices and Edges:

$v = 5, e = 6$

Step 2: Check for Subgraph Homeomorphic to $K_5$ :

This graph is not $K_5$

Step 3: Apply Euler's Formula:

Assuming planarity: $v - e + f = 2$

5 - 6 + f = 2 \quad \Rightarrow \quad f = 3

The graph satisfies Euler's formula

Conclusion:

The graph is planar because it does not contain $K_5$ or $K_{3,3}$ , and it satisfies Euler's formula.

infoNote

Example 2: Checking a Non-Planar Graph

Problem:

Determine if $K_{3,3}$ is planar.

Step 1: Count Vertices and Edges:

$v = 6, e = 9$

Step 2: Apply Euler's Formula:

Assuming planarity: $v - e + f = 2$

6 - 9 + f = 2 \quad \Rightarrow \quad f = 5

This value is valid, so proceed to check for subgraphs

Step 3: Check for Crossings:

$K_{3,3}$ cannot be drawn without edges crossing (proved mathematically).

Conclusion:

$K_{3,3}$ is non-planar because it cannot be drawn without overlapping edges.

Note Summary

infoNote

Common Mistakes

Ignoring $K_5$ or $K_{3,3}$ subgraphs: Always check for these as indicators of non-planarity.
Misapplying Euler's Formula: Ensure the graph is connected before using $v - e + f = 2$
Forgetting the Outer Face: Include the outer region as a face when applying Euler's formula.
Assuming all cycles are Hamiltonian: Not all graphs with cycles are Hamiltonian; verify carefully.
Overlooking graph redrawing: Non-planar graphs can sometimes be made planar with edge rearrangements.

infoNote

Key Formulas and Concepts

Euler's Formula (Planar Graphs): $v - e + f = 2$
Kuratowski's Theorem:

Non-planarity is caused by $K_5$ or $K_{3,3}$ subgraphs.

Hamiltonian Cycle: A cycle that visits every vertex once and returns to the start.

Planarity Algorithm Simplified Revision Notes for A-Level Edexcel Further Maths Core Pure

10.2.3 Planarity Algorithm

Introduction to Planarity

Hamiltonian Cycle

Example:

Kuratowski's Theorem

Planarity Algorithm Steps

Worked Examples

Example 1: Checking Planarity of a Graph

Example 2: Checking a Non-Planar Graph

Note Summary

Common Mistakes

Key Formulas and Concepts

500K+ Students Use These Powerful Tools to Master Planarity Algorithm For their A-Level Exams.

Other Revision Notes related to Planarity Algorithm you should explore