Planar Graphs and the Definition of Planarity
What you'll learn: You'll discover what makes a graph "planar" and see how some graphs can be drawn without crossing edges while others cannot.
What Is a Planar Graph?
A planar graph is a graph that can be drawn in the plane (on a flat surface like paper) such that no two edges cross each other except at their endpoints (vertices). The key word here is can be—even if a graph looks tangled in one drawing, if there exists some way to redraw it without crossings, it's planar.
Think of it like untangling a necklace: just because the chain looks knotted doesn't mean it has to be knotted. If you can rearrange it to lie flat without any strand crossing another, the structure is fundamentally "planar."
Examples of Planar Graphs
- Complete graph K₄: Four vertices where every vertex connects to every other. You can draw this as a triangle with one vertex inside (or outside) and connect appropriately—no crossings needed.
- Cycles and trees: Any cycle graph (C_n) and any tree are planar because their simple structures allow flat layouts.
- The complete bipartite graph K₂,₃: Five vertices (two in one set, three in the other) with edges only between sets. This can be drawn without crossings.
Non-Examples: Non-Planar Graphs
- Complete graph K₅: Five vertices all connected to each other. No matter how you try to draw this, at least one pair of edges will cross.
- Complete bipartite graph K₃,₃: Three vertices in each set, all connected across sets. This is the classic "utility graph" (three houses, three utilities)—it's impossible to connect them all without crossings.
These are fundamentally non-planar; no clever redrawing can eliminate crossings.
Key Takeaway: A planar graph is one that can be drawn on a plane without edge crossings, regardless of how it initially appears; K₄ is planar, but K₅ and K₃,₃ are not.