Planar Graphs

Introduction

A planar graph is a graph that can be drawn on a plane without any edges crossing. Planarity is important in circuit design, map-making, and graph theory.

Definition

A graph G is planar if it can be embedded in the plane such that:

  • Vertices are distinct points
  • Edges are simple curves connecting vertices
  • No two edges cross except at vertices

Note: Same graph can have planar and non-planar drawings!

Examples

Example 1: K₄ is Planar

Non-planar looking drawing:

1---2
|\\ /|
| X |
|/ \\|
3---4

Planar drawing (no crossings):

    1
   /|\
  / | \
 2  |  3
  \ | /
   \|/
    4

K₄ is planar - can be drawn without crossings.

Example 2: Tree

All trees are planar.

    1
   / \
  2   3
 / \
4   5

No edges cross - trees are always planar.

Example 3: Cycle

All cycles are planar.

1 --- 2
|     |
4 --- 3

Simple cycle has no crossings.

Non-Planar Graphs

Example 1: K₅ (Complete graph with 5 vertices)

K₅ is NOT planar.

Any drawing has crossings

Kuratowski’s Theorem: K₅ is a forbidden subgraph for planarity.

Example 2: K₃,₃ (Complete bipartite)

K₃,₃ is NOT planar.

Three houses, three utilities problem:
Connect each house to each utility without crossing

Impossible! K₃,₃ is the smallest non-planar bipartite graph.

Euler’s Formula

The Formula

For a connected planar graph with:

  • v vertices
  • e edges
  • f faces (regions, including outer face)

Euler’s Formula: v - e + f = 2

Example 1: Square

1 --- 2
|     |
3 --- 4
  • v = 4 vertices
  • e = 4 edges
  • f = 2 faces (inside + outside)

Check: 4 - 4 + 2 = 2 ✓

Example 2: Triangle

  1
 / \
2---3
  • v = 3
  • e = 3
  • f = 2 (inside + outside)

Check: 3 - 3 + 2 = 2 ✓

Example 3: K₄

    1
   /|\
  / | \
 2--+--3
  \ | /
   \|/
    4
  • v = 4
  • e = 6
  • f = 4 (3 triangular + 1 outer)

Check: 4 - 6 + 4 = 2 ✓

Faces

Definition

A face is a region bounded by edges (including the unbounded outer region).

Degree of a Face

The degree of a face is the number of edges bounding it.

Example:

1 --- 2
|     |
3 --- 4
  • Inner face: degree 4
  • Outer face: degree 4

Handshaking Lemma for Faces

Theorem: Sum of all face degrees = 2e

Why? Each edge borders exactly 2 faces.

Inequalities for Planar Graphs

Inequality 1: Edge Bound

For a simple planar graph with v ≥ 3:

e ≤ 3v - 6

Proof sketch:

  • Each face has degree ≥ 3
  • Sum of face degrees = 2e
  • Therefore: 3f ≤ 2e → f ≤ 2e/3
  • Use Euler’s formula: v - e + f = 2
  • v - e + 2e/3 ≥ 2
  • 3v - 3e + 2e ≥ 6
  • e ≤ 3v - 6 ✓

Inequality 2: For Bipartite

For simple planar bipartite graph with v ≥ 3:

e ≤ 2v - 4

Why? Each face has degree ≥ 4 (no triangles in bipartite)

Using Inequalities to Prove Non-Planarity

Proving K₅ is Non-Planar

K₅ has:

  • v = 5
  • e = 10

Check inequality: e ≤ 3v - 6

  • 10 ≤ 3(5) - 6
  • 10 ≤ 15 - 6
  • 10 ≤ 9
  • False! ✗

Therefore, K₅ is not planar.

Proving K₃,₃ is Non-Planar

K₃,₃ has:

  • v = 6
  • e = 9
  • Bipartite (no odd cycles)

Check bipartite inequality: e ≤ 2v - 4

  • 9 ≤ 2(6) - 4
  • 9 ≤ 12 - 4
  • 9 ≤ 8
  • False! ✗

Therefore, K₃,₃ is not planar.

Kuratowski’s Theorem

Statement

A graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.

Subdivision: Insert vertices into edges (doesn’t change planarity)

Example: Subdivision

Original K₃:

  1
 / \
2---3

Subdivision (add vertex on edge):

  1
 / \
2   4
|   |
3---+

Still planar (just added vertex on edge).

Application

To prove non-planar:

  1. Find K₅ or K₃,₃ as subgraph
  2. Or find subdivision of K₅ or K₃,₃

Wagner’s Theorem

Alternative characterization:

A graph is planar ⟺ it contains no minor of K₅ or K₃,₃.

Minor: Delete/contract edges

Planarity Testing

Algorithms

Efficient algorithms exist:

  • Hopcroft-Tarjan algorithm: O(v)
  • Boyer-Myrvold algorithm: O(v)

Linear time! Can test large graphs efficiently.

Plane Graph vs Planar Graph

Planar graph: Can be drawn without crossings

Plane graph: Already drawn without crossings (specific embedding)

Example: K₄ is planar, but a specific drawing may be a plane graph.

Dual Graph

Definition

For a plane graph G, the dual graph G* has:

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

Example

Primal graph:

1 --- 2
|  f1 |
3 --- 4
(f2 = outer face)

Dual graph:

f1 --- f2

Properties

  • (G*)* = G (dual of dual is original)
  • If G is planar, so is G*
  • Edges in G* = edges in G

Applications

1. Circuit Board Design

Problem: Route wires without crossing

Solution: Check if routing graph is planar

2. Map Coloring

Problem: Color regions so adjacent regions have different colors

Solution: Convert to graph coloring (planar graphs need ≤ 4 colors)

3. Network Layout

Problem: Design network without cable crossings

Solution: Ensure network graph is planar

4. Graph Drawing

Problem: Draw graph nicely

Solution: Use planarity algorithms for better layouts

Four Color Theorem

Theorem: Every planar graph can be properly colored with at most 4 colors.

Significance:

  • Proved in 1976 (Appel & Haken)
  • First major theorem proved with computer assistance
  • Every map can be colored with 4 colors!

Five Color Theorem: Easier proof, every planar graph colorable with 5 colors.

Maximal Planar Graphs

Definition

A maximal planar graph is planar where adding any edge makes it non-planar.

Properties:

  • Every face is a triangle
  • e = 3v - 6 (maximum edges)
  • Also called triangulation

Example

K₄ is maximal planar:

    1
   /|\
  / | \
 2--+--3
  \ | /
   \|/
    4

All faces are triangles, can’t add more edges.

Outerplanar Graphs

Definition

A graph is outerplanar if it can be drawn with all vertices on the outer face boundary.

Properties:

  • Stronger condition than planar
  • e ≤ 2v - 3
  • Trees are outerplanar

Example

1 --- 2 --- 3
 \   / \   /
  \ /   \ /
   4     5

All vertices on outer boundary.

Key Points for Exams

  1. Planar: can draw without edge crossings
  2. Euler’s formula: v - e + f = 2
  3. Face: region bounded by edges
  4. Simple planar: e ≤ 3v - 6
  5. K₅ and K₃,₃: not planar (forbidden subgraphs)
  6. Kuratowski: planar ⟺ no K₅/K₃,₃ subdivision
  7. All trees are planar
  8. Four Color Theorem: planar graphs need ≤ 4 colors
  9. Dual graph: vertex per face
  10. Planarity testing: O(v) time algorithms exist

Practice Problems

  1. Use Euler’s formula for triangle. Verify v - e + f = 2.

  2. Is K₅ planar? Use edge inequality to prove.

  3. Is K₃,₃ planar? Use bipartite inequality.

  4. Draw K₄ without crossings.

  5. How many faces does a cube graph have?

  6. For planar graph with v=10, e=15, find f.

  7. Are all trees planar? Why?

  8. What’s the dual graph of a square?

  9. Maximum edges in simple planar graph with 8 vertices?

  10. True or False: Every planar graph can be colored with 3 colors.