Planar Graphs

Discrete Math · Axiom Academy

Exploring graphs that can be drawn without edge crossings, Euler's remarkable formula, and the forbidden structures that make graphs non-planar. The key word is "can be drawn." A graph might look non-planar in one drawing but actually be planar with a clever rearrangement. The drawing where no edges cross is called a planar embedding . For any connected planar graph drawn without crossings, there's a beautiful relationship between the number of vertices, edges, and faces (regions created by the drawing): This formula is incredibly powerful for proving whether graphs can be planar. It holds for any planar embedding of a planar graph! 3. Edge Bounds for Planar Graphs Euler's formula leads to powerful constraints on planar graphs. For a simple (no loops or multiple edges) planar graph with at least 3 vertices: This inequality is a quick test: if a graph has more than 3V - 6 edges, it cannot be planar! For example, K₅ (complete graph on 5 vertices) has 10 edges but 3(5) - 6 = 9, so K₅ is non-planar. The ultimate characterization of planar graphs comes from identifying exactly which structures prevent planarity: 5. Applications: Circuit Design Planar graphs have critical real-world applications, especially in VLSI circuit design:

This is the written version of the interactive lesson above. See the full Discrete Math course.