Why are Planar Graphs so Exceptional

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

There are many interesting generalizations of the notion of planar graphs (I mentioned quite a few in the mathoverflow answer and initiated a question to have a useful source for such extensions); let me mention two of them:

The direct high-dimensional analog

 k-dimensional simplicial complexes (or more general stratified topological spaces) that can be embedded in R^{2k}  

Elementary polytopes

I tried to propose the following analog of planar graphs (more precisely of 3-connected planar graphs):

An elementary d-polytope is defined by the property that when you triangulate every 2-face of the polytope by adding edges  then the number of edges you get is dn - {{d+1} \choose {2}} edges. (For every polytope the number of such edges is at least dn - {{d+1} \choose {2}}.)  Another way to say it is:

f_1(P)=f_{02}(P)-3f_2(P) = dn - {{d+1} \choose {2}}.

In this formula,  f_{02}(P) is the number of chains   F_o \subset F_2 of verices included in 2-faces. See this post for a further discussion of such counting of chains(flag) of faces. Let me mention that for every d-polytope, d \ge 3, the left hand side in the formula above is at least as large as the right hand side.

Elementary d-polytopes and their graphs can be regarded as extensions of 3-polytopes and their graphs. Elementary polytopes form an interesting class of polytopes that include all 3-dimensional polytopes. It is known (but is not at all easy to prove) that the dual of an elementary polytope is elementary.

About these ads
This entry was posted in Combinatorics, Convex polytopes. Bookmark the permalink.

2 Responses to Why are Planar Graphs so Exceptional

  1. Not only do interesting questions arise by considering the special class of planar graphs but additional special issues arise when one considers a specific plane drawing of a planar graph. This is because when a graph is drawn in the plane it becomes possible to order or number, say for example, the edges at a particular vertex of the graph, in an organized consistent way. One example of results which started from this reality for plane graphs is this paper of Grunbaum and Motzkin:

    B. Grünbaum and T. S. Motzkin , The number of hexagons and the simplicity of geodesics on certain polyhedra. Canad. J. Math. 15 (1963), pp. 744–751.

    In this paper the following is explored (along with results about what today are called fullerenes). Suppose one has a 3-valent plane graph. If one picks any edge and moves along that edge (in either direction), when one gets to a vertex one has the choice of going left or right and moving on to another edge. Suppose one goes left, and at the next vertex in one’s “traversal” one goes right, alternating left, and right. Grunbaum and Motzkin refer to this as left-right path, and they prove that for a plane 3-valent graph with each of its faces having a multiple of 3 for its number of sides, that these left-right paths (starting on any edge) always generate “simple circuits.” I was able to extend this result in several directions. One such idea applies to the graph that serendipitously appears as the diagram that starts this “thread.” This graph is plane 4-valent, so when one moves along an edge and one gets to a vertex one might always choose to take the middle edge. For the graph above, when one does this, the graph breaks up into the union of simple closed curves. (It is easy enough to generate such graphs. Plop down a bunch of simple closed curves which cut each other when they meet transversely and think of the result as a 4-valent graph.) What are sufficient conditions for this (moving along middle edges to generate simple closed curves) to happen? Perhaps surprisingly, one such condition is that each of the faces of the plane 4-valent graph have a number of sides which is is a multiple of 3. What sometimes happens, which is an interesting phenomenon in its own right, is that one generates an eulerian circuit by always choosing the middle edge in a 4-valent plane graph. So the theorem I mentioned just a moment ago can be interpreted to say that there is no knot projection which results in a 4-valent graph all of whose faces have a multiple of 3 as their number of sides. (Knots would be eulerian when one moves along a middle edge.)

    I like to think of left-right (more precisely, far left, far right) paths (which makes sense for 4-valent graphs, too) or take the middle edge in a 4-valent graph as arising because one has numbered the edges from left to right as one gets to a vertex with the numbers 1, 2, 3. (Similarly, for 3-valent or 5-valent plane graphs.) Now one can ask a large number of questions about the behavior paths which obey a certain “code.” Left-right paths (4-valent case) are the code 1,3 while take the middle edge is the 2 code.

    Once more, because of the graph being planar (plane) one gets interesting mathematical ideas, and I suspect there are many interesting results and new ideas to be obtained from this line of thinking. So, yes, planar and plane graphs are exceptional.

  2. Gil Kalai says:

    Dear Joe, many thanks for your very interesting comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s