planargraph

Planar graph is a graph that can be drawn in the plane without edge crossings. A drawing with no crossings is called a planar embedding; a plane graph is a planar graph together with a distinguished embedding in the plane.

Euler's formula relates vertices, edges and faces: for a connected planar graph with n vertices, m edges and f faces, n − m + f = 2. More generally, for c connected components, n − m + f = c + 1.

Planarity can be characterized by forbidden subdivisions of K5 and K3,3 (Kuratowski's theorem): a finite graph is planar iff it does not contain a subgraph that is a subdivision of K5 or K3,3. Planar graphs are closed under taking subgraphs and minors.

Basic quantitative bounds: for a simple planar graph with n ≥ 3, m ≤ 3n − 6; if the graph is bipartite, m ≤ 2n − 4. Maximal planar graphs (triangulations) are those to which no edge can be added without losing planarity; they have m = 3n − 6 and all faces are triangles, and they are typically 3-vertex-connected for n ≥ 3.

Planarity testing and embeddings: there exist linear-time algorithms to decide planarity and produce planar embeddings, notably by Hopcroft and Tarjan (1974) and later Boyer and Myrvold (2004).

Applications and related classes: planar graphs arise in circuit layout and map drawing; many visualization problems are simplified on planar graphs. The Four Color Theorem states that every planar graph is vertex-4-colorable. Outerplanar graphs form a proper subclass with at most 2n − 3 edges.