Planar graph
A planar graph is a graph that can be embedded in the plane such that its edges intersect only at vertices where they are incident, with no crossings elsewhere.[1] Planar graphs form a fundamental class in graph theory, distinguished by their embeddability properties and connections to geometric and combinatorial structures.[2] For a connected planar graph with v vertices, e edges, and f faces in a plane embedding, Euler's formula states that v - e + f = 2.[3] This relation underpins many bounds on planar graphs, such as the fact that a simple planar graph satisfies e \leq 3v - 6 for v \geq 3.[4] A key characterization of planarity is provided by Kuratowski's theorem, which asserts that a finite graph is planar if and only if it contains no subgraph that is a subdivision of the complete graph K_5 or the complete bipartite graph K_{3,3}.[5] Equivalent formulations, such as Wagner's theorem using graph minors instead of subdivisions, highlight the structural obstructions to planarity.[6] Planar graphs also exhibit bounded chromatic numbers; the four color theorem proves that every planar graph can be properly vertex-colored with at most four colors, resolving a longstanding conjecture from the 19th century.[7] These properties have profound implications in areas like network design, VLSI layout, and computational geometry, where avoiding crossings optimizes embeddings and algorithms.[8] Testing planarity is efficiently solvable in linear time using algorithms based on these theorems.[9]Fundamentals
Definition
A planar graph is an undirected graph that can be embedded in the Euclidean plane such that no two edges intersect except possibly at their endpoints, which are the vertices.[2] Formally, given a graph G = (V, E), it is planar if there exists a mapping of vertices to points in \mathbb{R}^2 and edges to Jordan curves connecting those points, where curves only meet at shared endpoints and not otherwise.[10] In such an embedding, known as a plane graph, the vertices represent points, the edges represent the connecting curves, and the curves divide the plane into connected regions called faces, one of which is the unbounded outer face.[11] Edges in a planar embedding may be represented as curves, but by Fáry's theorem, every simple planar graph admits an equivalent embedding using straight-line segments between vertices without crossings.[12] Graphs that cannot be embedded in this manner are non-planar; the complete graph K_5 on five vertices and the complete bipartite graph K_{3,3} on two sets of three vertices each are the minimal examples of non-planar graphs, as any proper subgraph of either is planar.[13]Planar embeddings
A planar embedding of a graph is a representation of its vertices as distinct points in the plane and its edges as Jordan arcs connecting the corresponding points, such that no two arcs intersect except possibly at their endpoints, ensuring no edge crossings occur.[14] This drawing divides the plane into connected regions called faces, with the unbounded outer region designated as the exterior face.[15] Combinatorial embeddings abstract this geometric realization by focusing on the topological structure, specifying a rotation system that assigns a cyclic order to the edges incident to each vertex.[16] This rotation system uniquely determines the embedding up to homeomorphism of the plane, capturing the relative arrangement of edges around vertices without regard to specific positions or shapes.[17] In such an embedding, the boundaries of faces are well-defined walks along the edges, and for 2-connected planar graphs, each face boundary forms a simple cycle, ensuring no bridges or cut vertices disrupt the facial structure.[18] Geometric embeddings extend the combinatorial framework by assigning concrete positions and paths to vertices and edges while preserving the non-crossing property.[19] Polyline drawings allow edges to consist of multiple straight segments, providing flexibility in visualization.[20] Fáry's theorem establishes that every simple planar graph admits a straight-line embedding, where all edges are represented as single straight line segments between vertices, equivalent in topological type to any combinatorial embedding.[21] For 2-connected planar graphs, embeddings are unique up to reflection in the sense that the cyclic orders at vertices can be consistently reversed across the entire graph, corresponding to a mirror image of the drawing.[22] Whitney's theorem strengthens this for 3-connected planar graphs, asserting that any two embeddings are equivalent up to a homeomorphism of the plane that may include reflection, meaning the combinatorial structure is rigidly determined.[23]Planarity Criteria
Kuratowski's theorem
Kuratowski's theorem provides a fundamental characterization of planar graphs in terms of forbidden subgraphs. It states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of the complete graph K_5 or the complete bipartite graph K_{3,3}.[24] This criterion, published in 1930, offers a precise topological condition for planarity without requiring explicit embeddings.[25] The theorem emerged from Kazimierz Kuratowski's work on topological problems in his paper "Sur le problème des courbes gauches en topologie," where he addressed the embeddability of graphs on the plane by identifying obstructions to planarity.[24] Kuratowski's contribution built on earlier efforts to classify non-planar graphs, providing the first complete forbidden-subgraph theorem for planarity and influencing subsequent developments in graph minor theory.[26] A subdivision of a graph H is formed by replacing one or more edges of H with paths of positive length, where the internal vertices of these paths have degree two in the resulting graph.[25] Such subdivisions, also known as topological minors, preserve the connectivity structure of H while allowing for "stretched" edges. In contrast, a graph minor is a more general concept obtained from a graph by a sequence of edge deletions, vertex deletions, and edge contractions, where contracting an edge merges its endpoints into a single vertex and removes any resulting loops or multiple edges.[25] Every subdivision is a minor, but not vice versa, as contractions can simplify structures beyond mere path replacements. Kuratowski's theorem specifically uses subdivisions to capture topological obstructions to planarity. The proof of Kuratowski's theorem proceeds in two directions. The necessity—that any subdivision of K_5 or K_{3,3} renders a graph non-planar—follows from the fact that K_5 and K_{3,3} themselves are non-planar, and subdivisions preserve this property under planar embeddings.[27] For sufficiency, consider a minimal non-planar graph G with no such subdivisions; the proof uses edge deletions and contractions to reduce G to a base case. Specifically, deleting vertices or contracting edges in G yields a smaller graph that remains non-planar but must eventually contradict the absence of forbidden subdivisions, leading to an embedding via induction on graph size.[27] This approach highlights how deletions remove unnecessary structure and contractions handle branching, ensuring the characterization holds.[25] Illustrative examples of non-planar graphs often involve subdivisions of K_5 or K_{3,3}. The complete graph K_5 itself is a trivial subdivision and cannot be drawn without crossings due to its high density.[25] Similarly, K_{3,3}, with two partite sets of three vertices each connected by all possible edges, forces crossings in any attempted plane drawing. The Petersen graph, a famous 3-regular graph on 10 vertices, contains a subdivision of K_{3,3} but no subdivision of K_5, demonstrating its non-planarity via the theorem.[28] In the Petersen graph, one partite set corresponds to three outer vertices, the other to three inner vertices, with connecting paths formed by the graph's edges and spokes. This theorem has significant implications for recognizing non-planarity: to show a graph is non-planar, it suffices to identify a subdivision of K_5 or K_{3,3} as a subgraph, providing a direct and constructive method without needing full planarity testing algorithms.[25] Such identifications are often feasible for small or symmetric graphs, aiding theoretical and computational graph analysis.Wagner's theorem
Wagner's theorem provides a characterization of planar graphs in terms of graph minors. Specifically, a finite undirected graph is planar if and only if it contains neither the complete graph K_5 nor the complete bipartite graph K_{3,3} as a minor. This result was established by Klaus Wagner in 1937.[6] A minor of a graph G is obtained by a sequence of operations: deleting edges or isolated vertices, or contracting edges (merging two adjacent vertices into one and removing any resulting loops or multiple edges).[6] This contrasts with subdivisions, which involve only inserting degree-2 vertices along edges to form a topological minor, without allowing contractions or deletions beyond the subgraph itself.[29] The minor relation is thus broader and more flexible for structural analysis, as contractions can simplify graphs in ways subdivisions cannot.[6] Wagner's work built on Kuratowski's 1930 theorem by shifting from forbidden subdivisions to forbidden minors, proving their equivalence for planarity.[29] The proof proceeds in two directions: if a graph contains a subdivision of K_5 or K_{3,3} as a subgraph, contracting the subdivided edges yields K_5 or K_{3,3} as a minor, implying nonplanarity; conversely, any nonplanar graph contains such a subdivision by Kuratowski's theorem, which in turn implies a minor of K_5 or K_{3,3}.[29] Wagner's early insights into minors also anticipated the broader graph minor theory, including his conjecture that the minor relation forms a well-quasi-order on graphs, later proven by Robertson and Seymour in their extensive series of papers from 1983 to 2004.[6] The theorem's minor-based formulation has significant applications in the study of minor-closed graph families—classes of graphs excluding a fixed minor set—and their computational aspects. It identifies K_5 and K_{3,3} as the finite forbidden minor set for planarity, aligning with the general principle that every minor-closed family has a finite obstruction set, as established by the Robertson-Seymour theorem.[6] Algorithmically, testing whether a graph contains a fixed minor like K_5 or K_{3,3} can be done in O(n^3) time, enabling efficient planarity testing and membership queries for minor-closed families, though no single explicit algorithm covers all such families.[6]Other characterization theorems
One fundamental necessary condition for a connected graph to be planar is provided by Euler's formula, which relates the number of vertices v, edges e, and faces f (including the outer face) in any planar embedding: v - e + f = 2.[30] This criterion arises from the topology of the plane and holds for all connected plane graphs, though it is not sufficient on its own for determining planarity, as some non-planar graphs may also satisfy it when considering hypothetical embeddings.[30] Planar graphs also admit structural decompositions characterized by parameters like arboricity and thickness. The arboricity of a graph, defined via the Nash-Williams theorem as the minimum number of forests needed to partition its edges, is at most 3 for any planar graph; this follows from the density bound e \leq 3v - 6 for simple planar graphs with v \geq 3, implying \lceil e(H)/(v(H)-1) \rceil \leq 3 over all subgraphs H. While this provides a necessary condition, graphs with arboricity at most 3 are not necessarily planar. Thickness, the minimum number of planar subgraphs whose union covers all edges, equals 1 precisely for planar graphs, offering a direct but operational characterization tied to edge-partitioning algorithms.[31] Spectral methods offer algebraic characterizations of planarity. The Colin de Verdière invariant \mu(G) of a graph G, defined as the maximum corank of certain symmetric matrices associated with G satisfying specific strong Arnold properties, satisfies \mu(G) \leq 3 if and only if G is planar. This invariant captures topological restrictions through the multiplicity of the second-smallest eigenvalue of generalized Laplacians, providing a computable criterion that aligns with minor-closed properties. Separator theorems further characterize the recursive structure of planar graphs. The Lipton-Tarjan theorem states that every n-vertex planar graph has a vertex separator of size at most O(\sqrt{n}) that partitions the graph into two components each with at most $2n/3 vertices, enabling divide-and-conquer algorithms for planar graph problems. This property distinguishes planar graphs by their balanced separability, contrasting with denser graphs requiring larger cuts. Poset-theoretic approaches provide combinatorial characterizations. Schnyder's theorem asserts that a graph is planar if and only if the dimension of its incidence poset of vertices and edges is at most 3.[32] This links planarity to the minimum number of linear extensions needed to represent the poset, with applications to straight-line drawings. Geometric realizations offer another avenue. The Koebe–Andreev–Thurston theorem characterizes connected simple planar graphs as precisely those that admit a circle packing in the plane where circles correspond to vertices and tangencies to edges. For maximal planar graphs, such packings are unique up to Möbius transformations, facilitating conformal mappings and rigidity results. Post-2000 algebraic developments include criteria based on even subgraphs and cocycle spaces. A graph is planar if and only if it admits a drawing where every pair of non-adjacent edges crosses an even number of times, which can be tested algebraically via the vanishing of certain Pfaffians over the cycle space. This extends Hanani-Tutte theorems and provides a parity-based invariant for planarity detection.Structural Properties
Euler's formula
Euler's formula establishes a fundamental relationship among the vertices, edges, and faces of a connected plane graph, where a plane graph is a planar graph equipped with a specific embedding in the plane that realizes its planarity. Let v denote the number of vertices, e the number of edges, and f the number of faces, including the unbounded outer face. The formula states that v - e + f = 2. This relation, originally derived by Leonhard Euler in 1752 for the graphs of convex polyhedra, was generalized to arbitrary plane graphs by Augustin-Louis Cauchy in 1813 through stereographic projection of polyhedra onto the plane.[33][34] The formula can be proved by induction on the number of edges e. For the base case, consider a tree, which is a connected acyclic plane graph. A tree has e = v - 1 and bounds exactly one face (the outer face), so f = 1. Substituting yields v - (v - 1) + 1 = 2. Now assume the formula holds for all connected plane graphs with fewer than e edges. For a connected plane graph G with e edges, two cases arise. If G has a vertex of degree 1, remove that vertex and its incident edge; the resulting graph G' is connected with v' = v - 1, e' = e - 1, and f' = f, so by the inductive hypothesis, v' - e' + f' = 2, which implies v - e + f = 2. Otherwise, G has minimum degree at least 2 and thus contains a cycle; remove an edge that lies on a cycle. Such an edge is incident to two distinct faces, and removing it merges those faces, yielding G' with v' = v, e' = e - 1, f' = f - 1. By induction, v - (e - 1) + (f - 1) = 2, so v - e + f = 2. This covers all cases for connected plane graphs with at least one edge, completing the induction.[30] For disconnected plane graphs with c connected components, the formula extends to v - e + f = 1 + c, where each additional component beyond the first contributes an extra 1 to the right-hand side (accounting for the single outer face shared among all components).[35] More generally, for embeddings of connected graphs on closed orientable surfaces of genus g (where the plane corresponds to g = 0), the Euler characteristic is \chi = v - e + f = 2 - 2g; multiply-connected surfaces, such as the torus with g = 1, thus have \chi = 0.[36] A key application derives a density bound for simple connected plane graphs (no loops or multiple edges) with v \geq 3. Since each face is bounded by at least three edges and each edge bounds at most two faces, it follows that $2e \geq 3f, so f \leq \frac{2e}{3}. Substituting into Euler's formula gives v - e + \frac{2e}{3} \leq 2, or v - \frac{e}{3} \leq 2, hence e \leq 3v - 6. This bound highlights the sparsity of planar graphs compared to non-planar ones.[30]Degree and density bounds
One of the key consequences of Euler's formula for connected simple planar graphs with v \geq 3 vertices and e edges is an upper bound on the number of edges. In any planar embedding, the faces satisfy the handshaking lemma for faces: the sum of the face degrees is $2e. Assuming no multiple edges, each face has degree at least 3, so $2e \geq 3f, where f is the number of faces. Substituting Euler's relation f = e - v + 2 yields $2e \geq 3(e - v + 2), which simplifies to e \leq 3v - 6.[37] This bound implies that the average degree $2e/v < 6, so every simple planar graph has average degree less than 6 and thus contains a vertex of degree at most 5.[37] For maximal planar graphs, where e = 3v - 6, the sum of degrees is $6v - 12. Considering \sum (6 - \deg(v)) = 12, and noting that vertices of degree at most 5 contribute at least 1 to this sum while those of degree at least 6 contribute at most 0, there can be at most 12 vertices of degree at most 5.[11] For bipartite planar graphs, the absence of odd cycles ensures every face has degree at least 4, leading to $2e \geq 4f and thus e \leq 2v - 4 for v \geq 3.[37] These density bounds highlight the sparsity of planar graphs compared to non-planar ones; for example, the complete graph K_5 has 10 edges but violates e \leq 3 \cdot 5 - 6 = 9, confirming its non-planarity. Asymptotically, the maximum number of edges in a simple planar graph on v vertices is $3v - 6, or approximately $3v.[37] Coin graphs, formed as tangency graphs of non-overlapping equal-radius disks in the plane, provide examples of dense planar graphs. Such packings achieve hexagonal arrangements where each disk touches at most 6 others, yielding maximum degree 6 and up to nearly $3v edges, saturating the density bound.[38]Dual graphs
In the context of a plane graph, the dual graph G^* of a connected plane multigraph G is constructed by creating a vertex for each face of G, including the outer face, and placing an edge between two vertices in G^* for every edge in G that separates the corresponding faces; if an edge in G is incident to the same face on both sides, it corresponds to a loop in G^*, and multiple edges in G sharing the same pair of faces yield multiple edges in G^*.[25][39] This construction ensures a bijection between the edges of G and G^*, with vertices of G^* corresponding to faces of G and faces of G^* corresponding to vertices of G.[25] The dual G^* is always a plane multigraph, inheriting a planar embedding from G by placing vertices inside their respective faces and routing dual edges across primal edges without crossings.[25][39] If G is 3-connected, its dual G^* is simple (no loops or multiple edges) and unique up to isomorphism, as the embedding of G is unique in this case.[25] Moreover, every connected plane multigraph admits a plane dual, and the double dual (G^*)^* is isomorphic to G.[39] Duality preserves Euler's formula: if G has v vertices, e edges, and f faces, then G^* has v^* = f vertices, e^* = e edges, and f^* = v faces, yielding v^* - e^* + f^* = f - e + v = 2 for embeddings on the sphere (or adjusted for the plane).[25][39] Duality facilitates applications in optimization, such as relating minimum cuts in G (as bonds) to maximum flows or cycles in the dual G^*, enabling shortest path algorithms in the dual to solve min-cut problems in the primal via duality between cycles and bonds.[25] In polyhedral graph theory, duals of 3-connected planar graphs correspond to dual polyhedra, as exemplified by the cube (whose graph has square faces) and its dual the octahedron (with triangular faces).[25] Self-dual graphs, where G \cong G^*, include the octahedral graph, which is isomorphic to its own dual.[39]Special Families
Maximal planar graphs
A maximal planar graph is a simple planar graph to which no edge can be added without creating a non-planar graph.[10] These graphs are equivalently defined as triangulations of the plane, meaning that in any planar embedding, every face, including the unbounded outer face, is bounded by exactly three edges.[11] Maximal planar graphs exhibit several key structural properties. For a graph with v \geq 3 vertices, the number of edges is precisely e = 3v - 6.[40] Every such graph with at least four vertices is 3-connected, and the minimum degree of any vertex is at least 3.[25] These properties ensure that the graph achieves the maximum possible edge density among simple planar graphs while remaining embeddable without crossings. Regarding embeddings, Whitney's theorem establishes that every 3-connected planar graph has a unique combinatorial embedding in the plane up to reflection; this applies directly to maximal planar graphs with at least four vertices, as they are 3-connected.[41] Furthermore, Steinitz's theorem characterizes these graphs as the 1-skeletons of convex polyhedra: a graph is isomorphic to the vertex-edge graph of a convex 3-dimensional polyhedron if and only if it is 3-connected and planar.[42] Consequently, maximal planar graphs admit straight-line drawings in the plane that realize the vertices as points in convex position corresponding to such polyhedra. Prominent examples include the tetrahedral graph, which is the complete graph K_4 and represents the simplest non-trivial maximal planar graph with four vertices.[43] Another is the icosahedral graph, the 1-skeleton of the regular icosahedron with 12 vertices, all faces triangular, illustrating the connection to Platonic solids.[44] The enumeration of maximal planar graphs has been extensively studied, particularly for unlabeled instances. The number of unlabeled maximal planar graphs on v vertices forms a known sequence, starting with 1 for v=3, 1 for v=4, 2 for v=5, 5 for v=6, and 14 for v=7, with asymptotic growth analyzed through symmetries and recursive constructions.[45]Outerplanar graphs
An outerplanar graph is a planar graph that admits a planar embedding in which all vertices lie on the boundary of the outer face.[46] This embedding ensures that the graph can be drawn without edge crossings and with every vertex incident to the unbounded region. Outerplanar graphs exhibit several key properties that distinguish them as a proper subclass of planar graphs. For a simple outerplanar graph with v \geq 3 vertices, the maximum number of edges is e \leq 2v - 3, a stricter bound than the e \leq 3v - 6 for general planar graphs.[47] They are also series-parallel graphs, meaning they can be constructed from a single edge by repeated series and parallel compositions, and they contain no K_4 minor.[46] Additionally, outerplanar graphs are precisely the graphs that are both K_4-minor-free and K_{2,3}-minor-free, where K_{2,3} is the complete bipartite graph with partitions of sizes 2 and 3.[48] Characterizations of outerplanar graphs extend beyond minor exclusions. A planar graph is outerplanar if and only if it has an embedding whose weak dual—formed by contracting each inner face to a vertex and connecting dual vertices if their faces share an edge—is a forest.[49] For 2-connected outerplanar graphs, this weak dual is specifically a tree.[50] In such embeddings, the outer face has degree equal to the number of vertices, and no inner face has degree exceeding 3 in maximal cases. Examples of outerplanar graphs include cycles, which form the simplest non-trivial instances with all vertices on a single face; trees, which are outerplanar as they have no cycles and can be embedded with all vertices on the outer boundary; and fan graphs, consisting of a central vertex connected to all vertices of a path, embeddable with the path on the outer face and the central vertex also on it.[46] These graphs find applications in VLSI design, where their series-parallel structure allows efficient, fault-tolerant layouts in small areas with bounded wire lengths.[51] All outerplanar graphs are planar, as the required embedding is a special case of planar embedding, but the converse does not hold; for instance, K_4 is planar but not outerplanar, since any embedding places at least one vertex inside the outer face.Halin graphs
A Halin graph is formed by embedding a tree with no degree-two vertices and at least four vertices in the plane without edge crossings, then connecting its leaves in cyclic order determined by the embedding to form a cycle that avoids crossing any tree edges. This construction, introduced by Rudolf Halin in his investigation of minimally 3-connected graphs, yields a plane graph consisting of the tree and the added cycle. Halin graphs are planar by their embedding and 3-vertex-connected, as removing any two vertices leaves the graph connected due to the tree structure and the encircling cycle. Key properties of Halin graphs include strong Hamiltonicity: every Halin graph on at least four vertices admits a Hamiltonian cycle, and moreover, it is 1-Hamiltonian, remaining Hamiltonian after deletion of any single vertex. They are also Hamiltonian-connected, possessing a Hamiltonian path between any pair of distinct vertices. Halin graphs form a minor-closed family under the operation of taking graph minors; while they exclude the non-planar K_{3,3} minor, they frequently contain the K_4 minor, as seen when the tree includes a vertex of degree at least three adjacent to leaves. Representative examples of Halin graphs include wheel graphs, constructed from a star tree where the central vertex connects to all leaves forming the outer cycle, and the triangular prism graph, derived from a path of length two with three leaves connected cyclically. These examples illustrate the versatility of the construction, ranging from highly symmetric structures like wheels to more elongated forms based on elongated trees. Halin graphs find applications in graph drawing algorithms, where their tree-plus-cycle structure enables efficient straight-line drawings with bounded height relative to the number of vertices, facilitating compact visualizations of hierarchical data.Advanced Results
Graph enumeration
The enumeration of planar graphs involves counting both labeled and unlabeled instances, as well as their embeddings as planar maps, often leveraging recursive decompositions and generating functions derived from structural properties like connectivity levels. For labeled planar graphs on n vertices, exact counts can be obtained through recursive decompositions into 1-connected, 2-connected, and 3-connected components, allowing computation up to n=12. These decompositions rely on the unique embedding of 3-connected planar graphs (by Whitney's theorem) and map enumeration techniques.[52] The total number g_n grows asymptotically as g_n \sim g \cdot n^{-7/2} \gamma^n n!, where \gamma \approx 27.22688 and g \approx 4.2609 \times 10^{-6}; this estimate, including limit laws for parameters like the number of edges, was established using singularity analysis of generating functions.[53] For unlabeled planar graphs, exact enumeration is more challenging due to isomorphism considerations, but computational methods using orderly generation algorithms have determined the counts up to n=11. These numbers, obtained via programs like plantri for generating non-isomorphic instances, are as follows:| n | Number of unlabeled planar graphs |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 4 |
| 5 | 11 |
| 6 | 33 |
| 7 | 142 |
| 8 | 822 |
| 9 | 6966 |
| 10 | 79853 |
| 11 | 1140916 |