Planar graph

A planar graph admits a drawing in the plane whose edges meet only at common endpoints.

A planar map is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.

A face of a planar map is a connected component of the complement of its embedded graph. Its degree is the number of edge incidences around its boundary, counted with multiplicity, and the sum of all face degrees is twice the number of edges.

A rooted planar map is a planar map with a distinguished oriented edge called its root edge. Its tail is the root vertex, and the face on a chosen side of the edge may be designated as the root face.

A planar quadrangulation is a planar map in which every face has degree four, with incidences counted with multiplicity. A pointed quadrangulation additionally has a distinguished vertex.

The trivial bijection sends a rooted planar map with $n$ edges to a rooted planar quadrangulation with $n$ faces. Put one new vertex in each face and, in each corner, connect that face vertex to the incident original vertex. Each original edge then lies inside one quadrangular face; deleting the original edges gives the quadrangulation. The face bipartition recovers the original vertices and hence the inverse map.

A planar dual graph has one vertex in each face of a fixed planar embedding and one dual edge crossing each primal edge.

For a fixed finite plane graph, the complementary dual configuration opens a dual edge exactly when its primal edge is closed. Its components correspond to faces of the spanning open primal graph. The componentwise Euler formula for a connected planar graph gives the displayed identity. The outer face and isolated primal vertices are included; the identity also handles disconnected graphs, bridges and loops.

In planar bond percolation, declare a dual edge open exactly when the primal edge it crosses is closed. Independent primal parameter $p$ then gives independent dual parameter $1-p$.

For a rectangle in a planar lattice, exactly one of an open primal left-to-right crossing and a closed dual top-to-bottom crossing occurs.

For the lattice rectangle with graph vertices $\{0,\dots ,n\}\times \{0,\dots ,n-1\}$, let $H_n$ be an open left-to-right crossing. Its complementary event is a closed dual top-to-bottom crossing. The dual crossing rectangle has width $n-1$ and height $n$, so rotation and translation identify it with the original rectangle. Boundary edges along the starting and ending sides do not affect the crossing event. At $p=1/2$ the primal and dual edge states have identical laws, henceThe one-unit adjustment in the side lengths makes the symmetry exact rather than an informal assertion about a finite graph vertex square.

For a connected planar graph with $n$ vertices, $e$ edges, and $f$ faces,Deleting a cycle edge preserves connectedness and decreases both $e$ and $f$ by one, reducing the formula to its immediate tree case.

A simple planar graph with $n\ge 3$ vertices has at most $3n-6$ edges.

If every face of a connected planar graph has size at least $g>2$, double-counting edge-face incidences and using Euler's formula gives

Let a connected bridgeless planar graph have $n\ge 4$ vertices, $e$ edges, no four-cycle, and $t$ triangular faces. If no edge borders two triangular faces, thenso $f\le 8e/15$. The Euler formula for a connected planar graph then gives

The icosidodecahedral graph is the skeleton of the icosidodecahedron. It has 30 vertices, 60 edges, 20 triangular faces, and 12 pentagonal faces. Every edge separates a triangle from a pentagon, so it attains equality in the triangle-pentagon planar edge bound.