(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 nonplanar 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_{5} (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.
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
Every planar graph is 4partite, or 4colorable; this is the graphtheoretical formulation of the four color theorem.
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.
Search Encyclopedia
