Planar Graphs

Definition

A planar graph is a graph that can be embedded in the plane so that no edges intersect except at their common vertices.

• A particular drawing of a graph with no edge crossings is called a planar embedding.
• A graph is planar if at least one such embedding exists.
• A graph that has been drawn in the plane without crossings is called a plane graph.

Example

• A triangle graph $K_3$ is planar because it can be drawn as a triangle with no crossings.
• The complete graph $K_5$ is not planar because no matter how it is drawn, at least one pair of edges must cross.
• The complete bipartite graph $K_{3,3}$ is also non-planar.

Main Content

1. Planar Embedding and Faces

• A planar embedding is a drawing of a graph in the plane where edges meet only at their endpoints. Different drawings of the same graph may or may not be planar, but the graph is planar if at least one drawing works.
• The regions formed by the edges in a planar drawing are called faces. One of these faces is the unbounded outer face, while the others are bounded faces. Faces are essential for proving many planar graph properties.

Example

Consider a square with one diagonal:

A ----- B
| \     |
|   \   |
|     \ |
D ----- C

This drawing has no edge crossings, so it is planar. The diagonal divides the square into multiple faces.

2. Euler’s Formula and Consequences

• For any connected planar graph, the number of vertices $V$, edges $E$, and faces $F$ satisfy Euler’s formula:

$$V - E + F = 2$$

• This formula is a fundamental result in planar graph theory. It is used to derive many useful limits and inequalities, such as bounds on the number of edges a planar graph can have.

Important consequences

• If a connected planar graph has at least 3 vertices, then:

$$E \leq 3V - 6$$

• If the planar graph is triangle-free (contains no cycles of length 3), then:

$$E \leq 2V - 4$$

These inequalities help prove that some graphs cannot be planar.

Example

For a planar graph with $V = 6$, the maximum possible number of edges is:

$$E \leq 3(6) - 6 = 12$$

If a graph on 6 vertices has 13 or more edges, it cannot be planar.

3. Non-Planar Graphs and Kuratowski’s Theorem

• Two graphs are especially important as the basic examples of non-planar graphs:
• $K_5$: the complete graph on 5 vertices
• $K_{3,3}$: the complete bipartite graph with parts of size 3 and 3

Kuratowski’s Theorem

• states that a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$.

A subdivision means replacing edges by paths with additional vertices inserted.

Why this matters

• This theorem gives a complete characterization of planar graphs.
• It is a major tool for checking planarity in graph theory.
• If a graph contains a hidden $K_5$-like or $K_{3,3}$-like structure, it is non-planar.

Example

The graph $K_{3,3}$ can be represented as:

u1 ----- v1
 | \     / |
 |  \   /  |
 |   \ /   |
 |   / \   |
 |  /   \  |
 | /     \ |
u2 ----- v2
 | \     / |
 |  \   /  |
u3 ----- v3

No matter how it is drawn, some edges must cross. Hence it is non-planar.

Working / Process

1. Draw the graph carefully

• Try to place vertices in the plane in a way that reduces edge crossings.
• Rearrange vertices if necessary and check whether all edges can be drawn without intersection.

2. Apply planar tests

• Use Euler’s formula and edge bounds to test planarity.
• If the graph violates $E \leq 3V - 6$, it is definitely non-planar.
• For bipartite graphs, also check $E \leq 2V - 4$.

3. Search for forbidden subgraphs

• Look for a subdivision of $K_5$ or $K_{3,3}$.
• If such a subdivision exists, the graph is non-planar.
• If none exists and a valid drawing is possible, the graph is planar.

Advantages / Applications

Map coloring and geography

• Planar graphs are used to model maps, where regions correspond to faces and adjacent regions share boundaries.

Circuit and network design

• Planarity helps in designing printed circuit boards and wiring layouts with fewer crossings, which reduces complexity and interference.

Algorithm and visualization

• Planar graph properties are used in efficient graph drawing, computer graphics, and many optimization algorithms.

Summary

• Planar graphs can be drawn without edge crossings.
• Euler’s formula gives powerful relationships among vertices, edges, and faces.
• $K_5$ and $K_{3,3}$ are the key forbidden structures for planarity.
• Planar graph ideas are widely used in maps, circuits, and graph drawing.