What are Planar Graphs?

Graph Theory · Axiom Academy

Can you solve the classic utilities puzzle? Some graphs can be drawn flat, others cannot! Let's start with a simple graph. Three houses need to connect to one utility (water). Can you connect all three houses to the water without any lines crossing? Now here's the famous puzzle: Three houses each need connections to three utilities (water, gas, and electricity). Try to connect each house to each utility without any lines crossing! Step 3: What Makes a Graph Non-Planar? Let's compare different graph structures. Some can be drawn flat, others cannot. A graph is planar if it can be drawn on a flat surface (plane) with no edges crossing. Examples: trees, cycles, grids, K₄. A graph is non-planar if every drawing has at least one crossing. The smallest non-planar graphs are K₅ and K₃,₃—these are the "forbidden structures" of planarity! A graph is planar if and only if it does not contain a subdivision of K₅ or K₃,₃ as a subgraph. This gives us a complete characterization of planarity!

This is the written version of the interactive lesson above. See the full Graph Theory course.