Encyclopedia > Planar graph

  Article Content

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 K5 (the full graph on 5 vertices) or K3,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

ve + 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... a harmless waste of money (plus a possible placebo effect). Numerous diet programs use people's concern over their image, as a way to make money. They sell books an ...

This page was created in 37.1 ms