Planarity Testing Examples

Graph Theory · Axiom Academy

EXAMPLE Planarity Testing Examples Master techniques for determining if a graph can be drawn without edge crossings Problem: Determine if this graph is planar Excellent work! You've mastered planarity testing techniques. Here's what we learned: Edge Bound Test: For a planar graph with n vertices and m edges, we must have m ≤ 3n - 6 (for n ≥ 3). This provides a quick necessary condition for planarity. Kuratowski's Theorem: A graph is non-planar if and only if it contains a subdivision of K₅ (complete graph on 5 vertices) or K₃,₃ (complete bipartite graph with 3 vertices in each part). Systematic Redrawing: When testing planarity constructively, place vertices strategically and add edges one at a time, checking for conflicts. Use Jordan curve theorem insights. Multiple Verification Methods: Combining edge counting, forbidden subgraph detection, and redrawing attempts provides robust planarity verification. Face Formula: For connected planar graphs, Euler's formula v - e + f = 2 relates vertices, edges, and faces, providing another verification tool. These techniques form the foundation of graph drawing algorithms and topological graph theory. Practice identifying K₅ and K₃,₃ subdivisions to build intuition!

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