Harrison Brown asked the problem “Why are planar graphs so exceptional” over mathoverflow, and I was happy to read it since it is a problem I have often thought about over the years, as I am sure have many combinatorialsists and graph theorists. Harrison was interested in comparing planar graphs to graphs embedded in other surfaces.

It will be nice to discuss this question further here (mathoverflow is not an ideal platform for discussions, but some interesting ones have emerged.) So let me offer my answer. Another interesting answer was offered by Joseph Malkevitch.

## Three exceptional characteristics of planar graphs

**Duality:** Perhaps duality is the crucial property of planar graphs. There is a theorem asserting that the dual of a graphic matroid M is a graphic matroid if and only if M is the matroid of a planar graph. In this case, the dual of M is the matroid of the dual graph of G. (See this wikipedia article). This means that the circuits of a planar graph are in one to one correspondence with cuts of the dual graph.

One important manifestation of the uniqueness of planar graphs (which I believe is related to duality) is Kasteleyn’s formula for the number of perfect matchings and the connection with counting trees.

**Robust geometric descriptions:** Another conceptual difference is that (3-connected or maximal) planar graphs are graphs of convex 3-dimensional polytopes and thus have extra geometric properties that graphs on surfaces do not share. (This is Steinitz’s theorem.)

The geometric definition of planar graphs (unlike various generalizations) is very robust. A graph is planar if it can be drawn in the plane such that the edges are represented by Jordan curves and do not intersect in their interiors; the same class of planar graphs is what we get if we replace “Jordan curves” by “line intervals,” or if we replace “no intersection” by “even number of crossings”. The Koebe-Andreev-Thurston theorem allows us to represent every planar graph by the “touching graph” of nonoverlapping circles. Both (related) representations, via convex polytopes and by circle packing, can respect the group of automorphisms of the graph and its dual.

**Simple inductive constructions.** Another exceptional property of the class of planar graphs is that planar graphs can be constructed by simple inductive constructions. (In this respect they are similar to the class of trees, although the inductive constructions are not as simple as for trees.) This fails for most generalizations of planar graphs.

A related important property of planar graphs, maps, and triangulations (with labeled vertices) is that they can be enumerated very nicely. This is Tutte theory. (It has deep extensions to surfaces.)

It is often the case that results about planar graphs extend to other classes. As I mentioned, Tutte theory extends to triangulations of other surfaces. Another example is the fundamental Lipton-Tarjan separator theorem, which extends to all graphs with a forbidden minor.

## Two interesting generalizations

Continue reading →