Planar Graph

A planar graph is a graph that can be drawn on a plane without any edges crossing. The study of planar graphs is central to graph theory, topology, and combinatorics, and it provides the mathematical foundation for the Four-Color Theorem. Every planar graph divides the plane into regions called faces, and the relationship between vertices, edges, and faces is governed by Euler's formula for planar graphs: V - E + F = 2. The restriction to planar graphs dramatically simplifies certain computational problems — for instance, planar graphs are always 4-colorable, and many NP-hard problems on general graphs become solvable in polynomial time when restricted to planar embeddings. Yet the apparent simplicity of planar graphs conceals deep structural complexity, as demonstrated by the elaborate proofs required to establish their coloring properties. The theory of planar graphs connects to map coloring, circuit design, and the study of polyhedra, suggesting that the constraint of planarity is not a limitation but a productive source of mathematical structure.