Course contentsShow
← Computer Science
Lesson 692 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Planar Graphs

Learning about graphs that can be drawn on a plane without edge crossings and Euler's formula.

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.