Planar Graphs
You'll learn what planar graphs are and discover the famous relationship between their vertices, edges, and faces.
What Makes a Graph Planar?
A planar graph is a graph that can be drawn on a flat surface (like a piece of paper) without any edges crossing each other. Think of it like drawing a map of cities and roads—if you can draw all the roads without any going over or under each other, you have a planar graph!
Not all graphs are planar. For example, if you try to connect five cities where every city has a direct road to every other city (a complete graph K₅), you'll find it's impossible to draw without crossings.
Real-World Examples
- Circuit board layouts: Components connected by wires that can't overlap
- City planning: Streets that intersect only at designated crossings
- Network topology: Physical cable layouts that avoid crossings
Euler's Formula: The Mathematical Relationship
For any connected planar graph, there's a beautiful relationship discovered by mathematician Leonhard Euler:
V - E + F = 2
Where:
- V = number of vertices (nodes)
- E = number of edges (connections)
- F = number of faces (regions created, including the outer infinite region)
For example, imagine a triangle drawn on paper: 3 vertices, 3 edges, and 2 faces (inside the triangle and outside). Check: 3 - 3 + 2 = 2 ✓
Testing for Planarity
Common non-planar graphs include:
- K₅: Complete graph with 5 vertices
- K₃,₃: Complete bipartite graph with 3 vertices on each side
If a graph contains either of these as a substructure, it's non-planar.
Key Takeaway: A planar graph can be drawn without edge crossings, and every connected planar graph satisfies Euler's formula V - E + F = 2, revealing a fundamental relationship between its structure and geometry.