Planar Graphs

Definition

A graph is planar if it can be drawn in the plane without edge crossings.

Such a drawing is called a planar embedding or plane graph.

Euler's Formula

For a connected planar graph: $|V| - |E| + |F| = 2$

where:

• $|V|$ = number of vertices
• $|E|$ = number of edges
• $|F|$ = number of faces (including the unbounded outer face)

Examples

Triangle ($K_3$): $3 - 3 + 2 = 2$ ✓

Square ($C_4$): $4 - 4 + 2 = 2$ ✓

$K_4$ (tetrahedron): $4 - 6 + 4 = 2$ ✓

Generalization for Disconnected Graphs

If graph has $c$ connected components: $|V| - |E| + |F| = 1 + c$

Consequences of Euler's Formula

Edge Bound

For a connected planar simple graph with $|V| \geq 3$: $|E| \leq 3|V| - 6$

Proof: Each face has $\geq 3$ edges, and each edge borders 2 faces. So $2|E| \geq 3|F|$, giving $|F| \leq \frac{2|E|}{3}$. Substituting into Euler's formula and solving.

Edge Bound (No Triangles)

If the graph has no cycles of length 3: $|E| \leq 2|V| - 4$

Corollary

Every planar graph has a vertex of degree at most 5.

Proof: If all degrees $\geq 6$, then $2|E| = \sum d(v) \geq 6|V|$, so $|E| \geq 3|V|$. But this contradicts $|E| \leq 3|V| - 6$.

Non-Planar Graphs

$K_5$ is Not Planar

$K_5$ has 5 vertices and 10 edges. $3(5) - 6 = 9 < 10$, violating the edge bound.

$K_{3,3}$ is Not Planar

$K_{3,3}$ has 6 vertices, 9 edges, and no triangles. $2(6) - 4 = 8 < 9$, violating the triangle-free bound.

Kuratowski's Theorem

A graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

Subdivision

A subdivision of $G$ replaces edges with paths.

Wagner's Theorem (Equivalent)

A graph is planar if and only if it has no $K_5$ or $K_{3,3}$ minor.

Minor

$H$ is a minor of $G$ if $H$ can be obtained by deleting vertices/edges and contracting edges.

Planarity Testing

Algorithm

Can be tested in $O(|V|)$ time using algorithms like:

• Path addition method
• PQ-trees
• Left-right planarity testing

Dual Graphs

For a plane graph $G$, its dual $G^*$ has:

• One vertex for each face of $G$
• Edge between vertices if corresponding faces share an edge

Properties

• $(G^*)^* = G$ for connected plane graphs
• If $G$ is connected planar, $|V(G^*)| = |F(G)|$

Face Degrees

The degree of a face is the number of edges on its boundary (counting edges twice if traversed twice).

$\sum_{\text{faces } f} \deg(f) = 2|E|$

(Each edge contributes to exactly 2 faces)

Graph Thickness

The thickness of a graph is the minimum number of planar subgraphs whose union gives the graph.

$\theta(K_n) = \left\lceil \frac{n + 7}{6} \right\rceil \text{ for } n \geq 3$

Outerplanar Graphs

A graph is outerplanar if it has a planar embedding with all vertices on the outer face.

Characterization

$G$ is outerplanar iff it contains no $K_4$ or $K_{2,3}$ subdivision.

Edge Bound

$|E| \leq 2|V| - 3$

Chromatic Number

Every outerplanar graph is 3-colorable.

Applications

Circuit Design

Planar graphs can be implemented on a single layer without wire crossings.

Map Coloring

Maps are planar graphs (regions as vertices, edges for adjacent regions).

Network Layout

Planar networks are easier to visualize and implement.

Graph Drawing

Fáry's Theorem

Every planar graph can be drawn with straight-line edges.

Tutte's Theorem

Every 3-connected planar graph has a convex drawing (all faces are convex polygons).

Crossing Number

For non-planar graphs, the crossing number $\text{cr}(G)$ is the minimum number of crossings in any drawing.

• $\text{cr}(K_5) = 1$
• $\text{cr}(K_{3,3}) = 1$
• $\text{cr}(K_n) \sim \frac{1}{64}n^4$ (asymptotically)