Planar graph

In graph theory, a planar graph is a graph that can be drawn on a piece of paper so that no edges intersect. For example, the following two graphs are planar:

       

(the second one can be redrawn without intersecting edges by moving one of the inside edges to the outside), while the two graphs shown below are not planar:

       

It is not possible to redraw these without edge intersections. In fact, these two are the smallest non-planar graphs, a consequence of the characterization below.

The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs, now known as Kuratowski's theorem: a graph is planar if and only if it does not contain a subgraph which is an expansion of K₅ (the full graph on 5 vertices) or K_3,3 (six vertices, three of which connect to each of the other three, for a total of nine edges). An expansion of a graph results from inserting vertices into edges, i.e. changing an edge * --- * to * --- * --- *, and repeating this zero or more times. If, given the graphs A and B, and B which is an expansion of A, it is often described that A is homeomorphic to B.

In practice, Kuratowski's criterion cannot be used to quickly decide whether a given graph is planar. However, there exist fast algorithms for this problem: for a graph with n vertices, it is possible to determine in time O(n) whether the graph is planar or not.

explain that algorithm

Euler's formula states that if a connected planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer region), then

v − e + f = 2,

i.e. the Euler characteristic is 2. As an illustration, in the first planar graph given above, we have v=6, e=7 and f=3. If the second graph is redrawn without edge intersections, we get v=4, e=6 and f=4.

Every planar graph is 4-partite, or 4-colorable; this is the graph-theoretical formulation of the four color theorem.

Dual graph of a planar graph

For a planar graph G we may construct a graph whose vertices are the regions into which G divides the plane (including a single external region). The edges represent adjacency of regions: there is one for each edge of G, and can be shown as crossing it. The resulting graph G* is naturally also planar: it is called the planar dual graph, or just dual graph, with respect to the given plane embedding of G. We have G** = G, justifying the name dual.