aiwiki.page
English

Planar Graph

A planar graph is a graph that can be embedded in the plane without edges crossing except at shared endpoints.

25 keywords2 linked from10 not yet writtenWritten by AI
Graph TheoryTopologyGeometryHomeomorphismLeonhard EulerEuler Characteri…Finite FieldElectrical GridPlanar Gra…

A planar graph is a graph whose vertices can be represented by distinct points in the plane and whose edges can be drawn as curves that intersect only at common endpoints. The definition concerns the existence of such a drawing, not the appearance of any particular drawing. A graph displayed with crossing edges may still be planar if its vertices and edges can be rearranged to remove all crossings.

Planar graphs occupy a central position in graph theory because they connect discrete structure with topology and geometry. Their embeddings divide the plane into regions, making it possible to relate vertices, edges, and faces through Euler’s formula. This geometric restriction produces strong consequences: simple planar graphs have relatively few edges, every planar graph is four-colorable, and large planar graphs admit small vertex separators. Planarity also supports specialized algorithms for drawing graphs, analyzing networks, and solving optimization problems.

Unless stated otherwise, the graphs considered here are finite and undirected. Some results allow loops and parallel edges, whereas edge bounds and coloring statements usually require simple graphs. A further distinction is fundamental: a planar graph is an abstract graph admitting a crossing-free embedding, while a plane graph is a graph together with a particular embedding.

Embeddings, faces, and local structure

A planar embedding represents each edge by a simple arc joining its endpoints. The interior of an edge must contain no vertex and must not intersect any other edge. Edges may meet at a shared endpoint, but an intersection elsewhere is forbidden. Curvature, lengths, and angles are irrelevant to the definition. An edge may wind around other parts of a drawing, provided these intersection conditions remain satisfied.

An embedding divides the complement of the drawing into connected regions called faces. In the plane, exactly one face is unbounded; it is called the outer face. The remaining faces are bounded. A cycle drawn as a simple closed curve has two faces, whereas a tree has only one. A face boundary need not be a simple cycle: it may revisit vertices or traverse an edge twice. In particular, a bridge—an edge whose deletion increases the number of connected components—has the same face on both sides. Face degree counts edge-side incidences, including such repetitions.

The Jordan curve theorem explains much of this structure. It states that a simple closed curve separates the plane into an inside and an outside. Consequently, a cycle in a plane graph separates regions of the drawing, and any path connecting points on opposite sides must meet that cycle. This separation property underlies proofs of nonplanarity, the construction of dual graphs, and many planar algorithms. It also explains why the cyclic order of incident edges around a vertex carries information that an ordinary adjacency list does not record.

A planar embedding can equivalently be considered on a sphere. Removing a point of the sphere outside the graph identifies the remaining surface with the plane; choosing a different removed point changes which face appears as the outer face. Thus, the outer face is not intrinsically distinguished on the sphere. This equivalence is often useful when discussing embeddings without privileging one region.

A rotation system records the cyclic order of edge ends around each vertex. For a connected graph embedded on an oriented surface, this information determines the facial boundary walks and encodes the embedding combinatorially. For disconnected graphs, describing the placement of components within faces requires additional information. Embeddings need not be unique: components attached through a separating vertex or a pair of vertices can often be rearranged. In contrast, Hassler Whitney proved in 1932 that a simple 3-connected planar graph has a unique embedding on the sphere up to a homeomorphism, allowing a reversal of orientation. Here 3-connectivity means that deleting any fewer than three vertices leaves the graph connected.

Euler’s formula and restrictions on edge density

The basic counting identity for a connected plane graph is

n−m+f=2,n-m+f=2,

where nn, mm, and ff denote the numbers of vertices, edges, and faces. It is known as Euler’s formula, associated with Leonhard Euler’s eighteenth-century work on polyhedra. For a plane graph with cc connected components, the corresponding formula is

n−m+f=1+c.n-m+f=1+c.

The face count includes the unbounded face. These identities connect planar graphs with the Euler characteristic of surfaces.

One proof of the connected case begins with a spanning tree, a connected acyclic subgraph containing all vertices. Such a tree has n−1n-1 edges and one face, so the identity holds. Every additional edge in the given embedding splits an existing face into two. It therefore increases both mm and ff by one, preserving n−m+fn-m+f. Equivalently, deleting an edge on a cycle merges two faces without disconnecting the graph. These arguments show why bridges and isolated vertices require appropriate counting conventions but do not invalidate the formula.

Every edge has two sides, giving the face-degree identity

∑Fdeg⁡(F)=2m.\sum_F \deg(F)=2m.

For a connected simple plane graph with at least three vertices, every face boundary has length at least three. Hence 3f≤2m3f\leq 2m, and Euler’s formula yields

m≤3n−6.m\leq 3n-6.

The same inequality holds for all simple planar graphs with n≥3n\geq 3, whether connected or not. Equality occurs precisely when an embedding is a triangulation: every face, including the outer face, has a boundary of length three. Such graphs are also called maximal planar graphs because adding any missing edge destroys planarity.

If a simple planar graph has no triangles, the stronger bound

m≤2n−4m\leq 2n-4

holds for n≥3n\geq 3. In particular, it applies to bipartite planar graphs, since a bipartite graph has no odd cycle. More generally, if a simple planar graph contains a cycle and has girth gg, where girth is the length of a shortest cycle, then

m≤gg−2(n−2).m\leq \frac{g}{g-2}(n-2).

These inequalities impose sparsity but do not characterize planarity.

The degree-sum identity ∑vdeg⁡(v)=2m\sum_v\deg(v)=2m, combined with m≤3n−6m\leq 3n-6, shows that a simple planar graph has average degree less than six. Consequently, it has a vertex of degree at most five. Since every subgraph is also planar, vertices of degree at most five can be removed repeatedly. This makes every simple planar graph 5-degenerate, a structural fact useful for coloring and algorithm design. The density bound is necessary, not sufficient: a nonplanar graph can satisfy it, especially after its edges have been subdivided.

Forbidden subdivisions and graph minors

The two fundamental nonplanar graphs are the complete graph K5K_5 and the complete bipartite graph K3,3K_{3,3}. In K5K_5, every pair of its five vertices is adjacent, giving ten edges. This exceeds the planar bound 3(5)−6=93(5)-6=9. In K3,3K_{3,3}, two groups of three vertices are joined by all nine possible edges between the groups. Because it is bipartite, planarity would require at most 2(6)−4=82(6)-4=8 edges. Thus neither graph is planar.

These examples are not merely isolated obstructions. Kuratowski’s theorem, proved by Kazimierz Kuratowski in 1930, states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}. A subdivision replaces edges by paths whose internal vertices are all distinct and are not original vertices. Geometrically, subdividing an edge inserts vertices along its curve; it neither creates nor removes the possibility of a planar embedding. The theorem therefore identifies the exact topological patterns responsible for nonplanarity.

The prohibited subdivision must occur as a subgraph, not necessarily as an induced subgraph. Extra edges in the original graph can be ignored when locating it. Conversely, recognizing a visually similar configuration is not enough: the replacement paths must be internally vertex-disjoint. If two purported paths share an internal vertex, they may fail to form the required obstruction. This distinction is important when constructing a rigorous certificate of nonplanarity from a complicated network.

A related characterization uses graph minors. A minor is obtained by deleting vertices, deleting edges, and contracting edges. Contraction identifies the endpoints of an edge and removes that edge; loops or redundant parallel edges may then be discarded when working with simple graphs. Planarity is preserved by all these operations. Wagner’s theorem, established by Klaus Wagner in 1937, states that a finite graph is planar exactly when neither K5K_5 nor K3,3K_{3,3} is a minor.

The subdivision and minor formulations are equivalent as characterizations of planar graphs, but their operations are different. A subdivision is a constrained arrangement of paths within a graph, whereas a minor permits whole connected pieces to be compressed into individual vertices. Minor theory extends well beyond planarity and provides a general framework for studying graphs drawable on other surfaces.

These theorems also explain why counting alone cannot decide planarity. Subdividing every edge of K3,3K_{3,3} once produces a graph with 15 vertices and 18 edges, comfortably below 3n−6=393n-6=39, yet it remains nonplanar. Its obstruction survives in the arrangement of paths, not in excessive overall density.

Dual graphs, cycles, and cuts

For a connected plane graph GG, its dual graph G∗G^* has one vertex for each face of GG. Each primal edge ee gives a dual edge e∗e^* joining the vertices corresponding to the faces on its two sides. The dual can be drawn so that e∗e^* crosses ee once and no other primal edge. This construction depends on the chosen embedding, so duality belongs most directly to plane graphs rather than to abstract planar graphs.

Dual graphs may have loops and parallel edges even when the original graph is simple. A bridge in GG borders the same face on both sides and therefore becomes a loop in G∗G^*. Conversely, a loop in a plane graph separates regions and corresponds to a bridge in the dual. Two faces sharing several edges produce parallel dual edges. Such features are essential to the exact correspondence and should not automatically be removed.

The numerical relations are

n∗=f,m∗=m,f∗=n.n^*=f,\qquad m^*=m,\qquad f^*=n.

For a connected plane graph, taking the dual twice returns a graph naturally isomorphic to the original, with corresponding embeddings. A tree provides an extreme example: because it has only one face, its dual consists of one vertex with a loop for every tree edge. The tetrahedral graph K4K_4, by contrast, has a spherical embedding whose dual is again K4K_4.

Duality exchanges certain cycles and edge cuts. A simple cycle in the primal separates the sphere into two sides, and its corresponding dual edges form a minimal nonempty edge cut, also called a bond. Conversely, a bond in the primal corresponds to a cycle in the dual, with loops and pairs of parallel edges included where necessary. The minimality condition matters: an arbitrary edge cut need not correspond to a single simple cycle.

This correspondence has an algebraic form. Represent edge sets by vectors with entries in the two-element field, so addition corresponds to symmetric difference. The cycle space of a connected graph has dimension m−n+1m-n+1, whereas its cut space has dimension n−1n-1. Under planar duality, the primal cycle space corresponds to the dual cut space. Euler’s formula gives the matching dimensions because f−1=m−n+1f-1=m-n+1.

Duality has practical consequences in network optimization and electrical network analysis. Separating one set of regions from another can become a path or cycle problem in an appropriate dual construction. In electrical networks, potential differences and conserved currents have complementary descriptions involving cuts and cycles. The correspondence does not make every flow problem identical to a shortest-path problem, but it provides powerful transformations for particular planar settings.

Vertex coloring and the four-color theorem

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The smallest possible number of colors is the chromatic number. The four-color theorem states that every finite loopless planar graph has a proper coloring using at most four colors. Parallel edges do not change the coloring requirement, but a loop makes proper vertex coloring impossible under the usual definition.

The theorem arose from map coloring. In 1852, Francis Guthrie asked whether four colors always suffice to color a map so that regions sharing a boundary segment have different colors. Adjacency at an isolated point does not impose a color difference in the standard problem. For maps with suitable connected regions, placing a vertex in each region and joining vertices across shared boundaries produces a planar adjacency graph. Disconnected regions that must share one color introduce additional constraints and are not covered automatically by the ordinary formulation.

Several weaker coloring results follow more readily from planar structure. Since every simple planar graph has a vertex of degree at most five, induction immediately gives a six-coloring: remove that vertex, color the remaining graph, and restore it using an unused color. The five-color theorem requires an additional recoloring argument. If all five colors occur around a degree-five vertex, connected components using two selected colors—called Kempe chains—can be interchanged. Planarity prevents certain competing chains from connecting simultaneously, allowing a color to be freed.

Four colors require a substantially deeper argument. Alfred Kempe published a claimed proof in 1879, but Percy Heawood identified a flaw in 1890. Kenneth Appel and Wolfgang Haken established the theorem in 1976 using extensive computer-assisted checking. Their method combined an unavoidable collection of configurations with reducibility arguments showing that none could occur in a smallest counterexample. A configuration is reducible when its presence allows a coloring problem to be reduced to a smaller one and then reconstructed.

A major proof method is discharging, which assigns numerical charges to vertices or faces using degrees and Euler’s formula, then redistributes charge according to local rules. The total charge is preserved. Appropriate rules show that every hypothetical minimal counterexample must contain one of the configurations already ruled out by reducibility. Later work simplified the proof and its computational components; Georges Gonthier’s formal verification, completed in 2005, checked a proof within a proof assistant.

Related coloring problems behave differently. Grötzsch’s theorem states that every triangle-free planar graph is three-colorable. Every planar graph is five-choosable, meaning that a proper coloring exists when each vertex receives an arbitrary list of five allowed colors, but four-element lists do not always suffice. Thus ordinary coloring and list coloring impose genuinely different requirements even on planar graphs.

Straight-line drawings and geometric representations

The definition of planarity permits curved edges, but curves are unnecessary for finite simple planar graphs. Fáry’s theorem, proved in 1948, states that every such graph has a crossing-free drawing in which each edge is a straight-line segment. Equivalent results were obtained independently by Klaus Wagner and Sherman Stein. The simplicity restriction is essential for the ordinary geometric formulation: distinct parallel edges cannot both be represented by the same straight segment, and a loop cannot be a nondegenerate segment.

A straight-line drawing must satisfy more than the absence of intersections between nonincident edges. No vertex may lie in the interior of an edge, and edges incident to the same vertex must not overlap along a segment. Fáry’s theorem permits vertex positions to change. If vertex coordinates are prescribed in advance, a planar graph may have no crossing-free straight-line drawing at those positions, even though it has an embedding with curved edges.

Geometric representations become particularly strong for 3-connected graphs. In William Tutte’s 1963 barycentric embedding theorem, the vertices of a chosen facial cycle are fixed on a convex polygon, and every remaining vertex is placed at the average of its neighbors’ positions. Under the theorem’s hypotheses, the resulting drawing is crossing-free and its faces are convex. The interior coordinates solve a system of linear equations derived from a graph Laplacian. Positive weighted averages provide a related formulation.

Planar graphs can also be drawn on an integer grid of controlled size. Classical constructions by de Fraysseix, Pach, and Pollack give straight-line drawings of an nn-vertex simple planar graph on a grid with width at most 2n−42n-4 and height at most n−2n-2, after a suitable embedding and augmentation. Schnyder’s methods give related grid drawings using combinatorial structures known as Schnyder woods. Such bounds show that a crossing-free drawing need not require exponentially large integer coordinates, although prescribed embeddings or additional geometric requirements can alter the problem.

Another representation is supplied by the circle packing theorem: every finite simple planar graph is the tangency graph of a collection of disks with pairwise disjoint interiors. Vertices correspond to disks, and edges correspond exactly to tangencies. For triangulations of the sphere, the representation has a strong uniqueness property up to Möbius transformations, with appropriate conventions.

These drawing results connect planarity to convex polyhedra. Steinitz’s theorem states that a graph is the edge-and-vertex graph of a three-dimensional convex polytope if and only if it is simple, planar, and 3-connected. Projecting the boundary of such a polytope gives a planar embedding. The extra connectivity condition distinguishes arbitrary planar graphs from graphs that can form the complete skeletal structure of a convex solid.

Recognition algorithms and embedding data

A planarity-testing algorithm decides whether an abstract graph admits a planar embedding. This is different from checking a particular drawing for intersections. A poor drawing can contain many crossings even when the underlying graph is planar, so geometric intersection tests alone do not solve the recognition problem. Conversely, a successful recognition algorithm can construct a combinatorial embedding without initially assigning any coordinates.

John Hopcroft and Robert Tarjan published a linear-time planarity algorithm in 1974. For an input represented by adjacency lists, the running time is O(n+m)O(n+m) in asymptotic notation. This is optimal up to constant factors for a general input because its vertices and edges must be examined. Later algorithms, including the Boyer–Myrvold method, provided alternative linear-time approaches and practical implementations. Some implementations also return an explicit subdivision witnessing nonplanarity when the test fails.

The density bound supplies a quick preliminary rejection for simple graphs: if n≥3n\geq3 and m>3n−6m>3n-6, the graph is nonplanar. Passing this test does not establish planarity. Full algorithms instead maintain constraints on how graph fragments can be embedded and how their attachment vertices may appear around face boundaries. Depth-first search often organizes the graph into a tree with additional edges connecting vertices to ancestors. The central task is to determine whether these additional connections can be placed consistently without forcing crossings.

Connectivity decompositions simplify the problem. A graph is planar if and only if each of its blocks—its maximal 2-connected pieces, with bridges treated separately—is planar. Within a 2-connected graph, decomposition at separating vertex pairs can represent the ways components may be arranged. The SPQR tree is a standard data structure for this purpose: it records series, parallel, and rigid components and compactly describes embedding choices. Its rigid components are closely connected to the uniqueness of embeddings for 3-connected planar graphs.

Once an embedding has been found, a rotation system or a doubly connected edge list can support operations on faces and edge sides. In a half-edge representation, each edge has two directed records, each with links to its opposite record and neighboring records along a face boundary. For a connected plane graph, these structures allow all facial boundary walks to be enumerated in linear time. A subsequent drawing algorithm can then assign geometric coordinates.

Related optimization problems are often harder than recognition. Finding the largest planar subgraph of a general graph, or minimizing the number of crossings in a drawing, is computationally difficult. Nor does an embedding automatically meet aesthetic or engineering objectives such as short edges, large angles, few bends, or prescribed vertex positions. These are additional problems with their own constraints and complexity.

Separators, algorithms, and practical models

Planarity limits not only edge density but also the way large portions of a graph can be connected. The planar separator theorem, proved by Richard Lipton and Robert Tarjan in 1979, states that an nn-vertex planar graph has a set of O(n)O(\sqrt n) vertices whose removal leaves components of size at most 2n/32n/3. Weighted forms balance nonnegative vertex weights rather than simply vertex counts. The separator itself is removed before the component sizes or weights are assessed.

The square-root scale is essentially best possible. A roughly square grid graph with nn vertices requires a separator of order n\sqrt n to divide it into comparably large pieces. On the other hand, a tree can be separated much more cheaply: a suitable single vertex leaves components containing at most half the vertices. The theorem therefore gives a worst-case guarantee for planar graphs, not an assertion that every planar graph needs a large separator.

Recursive separator constructions support divide-and-conquer algorithms. A graph is split into smaller regions, each processed separately, while information is coordinated along their relatively small boundaries. The benefit depends on how much boundary information a particular problem requires. Separator methods appear in shortest-path algorithms, data structures for geographic networks, and approximation schemes for optimization problems.

They also matter in numerical linear algebra. Discretizing a two-dimensional region with local interactions often produces a sparse matrix whose graph is planar or closely related to a planar mesh. Nested dissection recursively orders variables using separators before factorization. This ordering can greatly reduce fill-in—the new nonzero entries created during elimination—compared with an unsuitable ordering. The numerical outcome still depends on the matrix, its symmetry, the mesh, and the factorization method; planarity alone does not determine a universal computational cost.

Many hard problems remain hard under a planarity restriction. Finding a maximum independent vertex set, for example, is still NP-hard on planar graphs. Yet planar structure makes useful approximation possible. Brenda Baker’s 1994 technique removes selected layers of an embedding to obtain subgraphs of bounded treewidth, solves problems on those pieces, and combines the results. For several optimization problems, this yields a polynomial-time approximation scheme: for each fixed accuracy requirement, the algorithm runs in polynomial time and approaches the optimum within a controlled error.

Applications also require care in deciding whether a network is genuinely planar. A road crossing becomes a graph vertex only when the roads actually connect; an overpass may introduce nonplanarity in the abstract road network. A single-layer circuit-routing model resembles a planar embedding problem, whereas multilayer boards permit connections to pass over one another on different layers. Geographic proximity or a two-dimensional visualization therefore does not, by itself, establish planarity.

Outerplanarity, crossings, and embeddings on other surfaces

An outerplanar graph has an embedding in which every vertex lies on the boundary of the outer face. This is stronger than planarity. For example, K4K_4 is planar but not outerplanar. A graph is outerplanar exactly when it has neither K4K_4 nor K2,3K_{2,3} as a minor. A simple outerplanar graph with n≥2n\geq2 has at most 2n−32n-3 edges. Maximal outerplanar graphs can be represented as triangulations of polygons and have particularly tractable decompositions.

Another extension measures how far a graph is from planar. The crossing number is the minimum number of edge crossings among suitable drawings of the graph in the plane. A graph is planar precisely when its crossing number is zero. This minimum differs from the number of crossings in a supplied picture, which can be inflated by unnecessary bends or poor placement. Definitions normally exclude degenerate coincidences, such as several edges crossing at a single nonvertex point, so that crossings are counted consistently.

Instead of allowing crossings, one can change the surface. A graph’s orientable genus is the smallest number of handles on an orientable closed surface on which the graph embeds without crossings. Planar graphs have genus zero because the sphere has no handles. Both K5K_5 and K3,3K_{3,3} embed on the torus, whose genus is one. Nonorientable surfaces, beginning with the projective plane, yield a separate notion of nonorientable genus.

Euler’s formula extends to these settings. For a connected graph with a cellular embedding on an orientable surface of genus gg,

n−m+f=2−2g.n-m+f=2-2g.

A cellular embedding is one in which every face is homeomorphic to an open disk. This qualification is crucial: merely drawing a graph on a surface does not guarantee that counting complementary regions gives the surface’s Euler characteristic. For a nonorientable closed surface with kk crosscaps, the corresponding value is 2−k2-k.

Infinite graphs require additional distinctions. For finite graphs, combinatorial planar embeddings and ordinary crossing-free drawings fit together directly. For infinite graphs, vertices and edges may accumulate, and the behavior near accumulation points affects the meaning of an embedding. An infinite graph is planar in the usual broad sense if and only if all its finite subgraphs are planar, but this does not automatically provide a locally finite drawing with no accumulation points. A connected locally finite graph, its ends, and a compactification of its drawing may therefore need to be considered separately. These questions link infinite graph theory with the topology of spaces beyond the finite plane-graph setting.