Admin: Create Planar Graphs page following the style of Graphs/Minimum_Spanning_Tree, covering Euler's Formula, Kuratowski's Theorem, planarity algorithms, and applications (via create-page on MediaWiki MCP Server)

2026-06-24T20:47:16Z

Create Planar Graphs page following the style of Graphs/Minimum_Spanning_Tree, covering Euler's Formula, Kuratowski's Theorem, planarity algorithms, and applications (via create-page on MediaWiki MCP Server)

New page

=Notes=

A '''planar graph''' is a graph that can be drawn in the plane without edge crossings — that is, it can be embedded in the plane so that edges intersect only at their common endpoints. A particular such drawing is called a '''planar embedding''', and a graph together with a fixed embedding is called a '''plane graph'''.

Planar graphs form one of the most deeply studied classes in graph theory, with connections to topology, combinatorics, and algorithm design. The subject is motivated by classic problems such as the Four Colour Problem and circuit layout design.

==Properties==

Two fundamental tools underpin the theory of planar graphs: Euler's Formula and Kuratowski's Theorem.

===Euler's Formula===

For a connected plane graph <math>G</math> with <math>n</math> vertices, <math>e</math> edges, and <math>f</math> faces (regions of the plane bounded by the embedding), Euler's Formula states:

<math>
n - e + f = 2
</math>

This is the workhorse for deriving structural constraints on planar graphs. For a disconnected plane graph with <math>k</math> components, the formula generalizes to <math>n - e + f = k + 1</math>.

From Euler's Formula, one obtains critical edge bounds:

* For any simple planar graph with <math>n \geq 3</math>: <math>e \leq 3n - 6</math>
* For any triangle-free simple planar graph: <math>e \leq 2n - 4</math>

These bounds immediately prove the nonplanarity of <math>K_5</math> (<math>e = 10 > 9 = 3n - 6</math>) and <math>K_{3,3}</math> (<math>e = 9 > 8 = 2n - 4</math>).

===Maximal Planar Graphs and Triangulations===

A simple planar graph is '''maximal''' if adding any new edge would destroy planarity. A '''triangulation''' is a plane graph in which every face boundary is a 3-cycle. For an <math>n</math>-vertex simple plane graph, the following are equivalent:

* <math>e = 3n - 6</math>
* The graph is a triangulation
* The graph is maximal planar

===Dual Graphs===

Given a plane graph <math>G</math>, its '''dual graph''' <math>G^*</math> has vertices corresponding to the faces of <math>G</math>, and edges corresponding to the edges of <math>G</math> — each dual edge crosses exactly one primal edge, connecting the two faces on either side.

Key duality relationships:
* A cycle in <math>G</math> corresponds to a bond (minimal edge cut) in <math>G^*</math>
* Deleting an edge in <math>G</math> corresponds to contracting the corresponding edge in <math>G^*</math>
* If <math>G</math> is connected, then <math>(G^*)^* \cong G</math>
* A plane graph is bipartite iff every face has even length iff <math>G^*</math> is Eulerian

===Kuratowski's Theorem===

The central characterization of planarity, proved by Kuratowski in 1930:

'''A graph is planar if and only if it does not contain a subdivision of <math>K_5</math> or <math>K_{3,3}</math>.'''

A '''subdivision''' of a graph replaces edges with independent paths. In other words, <math>K_5</math> and <math>K_{3,3}</math> are the two fundamental obstructions to planarity — this is a classic TONCAS ("The Obvious Necessary Condition is Also Sufficient").

===Wagner's Theorem===

Wagner (1937) gave an equivalent formulation using '''minors''' (a graph obtained by deleting and/or contracting edges):

'''A graph is planar if and only if it has neither <math>K_5</math> nor <math>K_{3,3}</math> as a minor.'''

This formulation connects planar graph theory to the broader theory of graph minors and ultimately to the Robertson–Seymour Graph Minor Theorem.

===Fáry's Theorem===

Every simple planar graph has a planar embedding in which all edges are straight line segments. For 3-connected planar graphs, Tutte's Theorem gives the stronger result that a convex embedding exists (every face bounded by a convex polygon).

Schnyder (1992) proved that every <math>n</math>-vertex planar graph has a straight-line embedding on the integer grid <math>[n-1] \times [n-1]</math>.

===Outerplanar Graphs===

A graph is '''outerplanar''' if it has an embedding in which every vertex lies on the boundary of the unbounded face. Every simple outerplanar graph has a vertex of degree at most 2. <math>K_4</math> and <math>K_{2,3}</math> are planar but not outerplanar.

==Coloring of Planar Graphs==

Planar graphs have strong coloring properties:

* '''Five Colour Theorem:''' Every planar graph is 5-colorable. Proved via Euler's Formula (a planar graph always has a vertex of degree at most 5) combined with induction.
* '''Four Colour Theorem''' (Appel and Haken, 1977): Every planar graph is 4-colorable. This was the first major theorem proved with essential computer assistance.

These results connect to [[Graphs/Colouring]].

==Algorithms==

===Planarity Testing===

Determining whether a graph is planar can be done in linear time. The first linear-time algorithms were given by Hopcroft and Tarjan (1974) and by Booth and Lueker (1976), both using a depth-first search approach.

Modern planarity testing typically uses one of two approaches:
* '''Path addition method''' (Hopcroft–Tarjan): incrementally adds paths to a planar embedding, testing at each step whether the addition maintains planarity.
* '''Vertex addition method''' (Booth–Lueker, also known as the PQ-tree algorithm): builds a planar embedding one vertex at a time, maintaining all possible orderings of edges around each vertex.

===Embedding Construction===

Given that a graph is planar, constructing a planar embedding also runs in <math>O(n)</math> time. A straight-line embedding can be constructed in <math>O(n)</math> time following de Fraysseix, Pach, and Pollack (1990).

===Crossing Number===

The '''crossing number''' <math>\operatorname{cr}(G)</math> is the minimum number of edge crossings in any drawing of <math>G</math> in the plane. A graph is planar iff <math>\operatorname{cr}(G) = 0</math>. Computing the crossing number is NP-hard in general, but bounds are known for complete graphs and complete bipartite graphs.

==Parameters of Planarity==

Beyond the binary question of planarity, several parameters measure "how far" a graph is from being planar:

* '''Thickness''' <math>t(G)</math>: the minimum number of planar subgraphs whose union is <math>G</math>. Planar iff <math>t(G) = 1</math>.
* '''Genus''' <math>\gamma(G)</math>: the minimum genus of an orientable surface on which <math>G</math> can be embedded without crossings. Planar iff <math>\gamma(G) = 0</math>. Euler's Formula generalizes to <math>n - e + f = 2 - 2\gamma(G)</math>.
* '''Skewness''': the minimum number of edges that must be deleted to obtain a planar subgraph.

==Applications==

Planar graphs have numerous practical applications:

* Circuit board and VLSI chip layout design (where wire crossings cause problems)
* Geographic maps and cartography (the Four Colour Problem originates here)
* Graph drawing and network visualization
* Facility layout and architectural design
* Road network design (most road networks are near-planar)
* Algorithms for planar graphs often admit faster solutions than for general graphs (e.g., shortest paths, maximum flow, separator theorems)

==Related Pages==

* [[Graphs/Colouring]] — vertex and edge colouring, including the Four Colour Theorem
* [[Graphs/Connectivity]] — k-connected graphs; 3-connected planar graphs have convex embeddings
* [[Graphs/Definitions]] — basic graph theory definitions
* [[Graphs/Data Structures]] — representations of graphs, including planar graphs
* [[Graphs/Minors]] — graph minors and the Robertson–Seymour theorem
* [[Graphs/Euler Tour]] — Euler's Formula connects to Euler tours via duality
* [[Introduction to Graph Theory/Planar Graphs]] — in-depth coverage from West's textbook

=Flags=

{{GraphsFlag}}

Graphs/Planar Graphs - Revision history

Admin: Create Planar Graphs page following the style of Graphs/Minimum_Spanning_Tree, covering Euler's Formula, Kuratowski's Theorem, planarity algorithms, and applications (via create-page on MediaWiki MCP Server)