Joe Malkevitch: Why Planar Graphs are so Exceptional

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.

This entry was posted in Combinatorics, Guest blogger. Bookmark the permalink.

6 Responses to Joe Malkevitch: Why Planar Graphs are so Exceptional

1. harrison says:

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.

Of course, strictly speaking you don’t always need the graph to be planar to take advantage of this — a cyclic ordering of the edges at each vertex given (I believe) by a planar drawing, possibly with crossing edges, is part of the definition of a dessin d’enfant.

2. daveagp says:

This reminded me of a section in a book I read… just looked it up… called “Herb Shank’s Milkman’s Route” by Ross Honsberger in the book “Mathematical Recreations: A Collection in Honor of Martin Gardner.”

It describes a certain construction of Shank from 1974 which gives a 2-vertex-coloured plane graph with the following property: starting from any arc, and making left turns at every L-coloured vertex and right turns at every R, you get an Eulerian dicircuit (covering every edge once in each direction, then ending where you started).

3. When Grunbaum and Motzkin thought about left-right paths, when following such a path if it did not close up into a simple circuit they “terminated” the path and did not really consider it further. However, one can think about tours which are left-right paths even when they self-intersect and form other patterns than simple circuit L-R tours. One just continues following L-R turns in a 3-valent graph (or there are further generalizations) until one “repeats” the pattern. One person who did this was the late Herb Shank (U. of Waterloo).

There is quite a large literature about these generalized L-R paths and and the “straight through” analogue for 4-valent graphs. These questions have connections with what are called Gauss Codes and for “bicycles.”

The references section (which you can see without seeing the paper itself) of the article whose url on the ACM Portal gives a wide variety of links to the papers that have done in this area includes several which Herb Shank wrote or co-authored:

http://portal.acm.org/citation.cfm?id=1467137

4. Igor from LA says:

Let me make a comment on the background of the Grünbaum-Motzkin paper. The idea is that Euler’s formula gives a simple linear relation on the numbers a(i) of i-sided faces of a planar cubic graph. This formula omits a(6) and the classical Eberhard’s theorem (of 1891) states that for every sequence a(i), there is a graph with these face numbers, except perhaps for a(6). Now, one would assume that the number of hexagons a(6) must satisfy only some inequalities, i.e. any large enough a(6) will work. Not so! In fact, Eberhard in his original article speculated that in the case only 3,6,9… -sided faces, the number of hexagons must always be even, which was eventually proved by the G-M theorem. It would be interesting, of course, to find other relations of this type. Gil, can your variations be stated in this form?

One last comment: there is a beautiful proof of (a generalization of) the G-M theorem via elementary group theory: http://www.pnas.org/cgi/reprint/52/1/44.pdf
This proof is so convincing, it really gives you the feeling that all results of this type should follow along similar lines, and possibly follow from a general result in geometric group theory.

5. Gil says:

Dear Igor, thanks. Indeed geometric/combinatorial groups theory seems quite related to planarity and related graph theory but I know very little about this connection. Here is a recent paper by Riley and Thurston on a problem about planar graphs related to geometric group theory. http://front.math.ucdavis.edu/0511.5493 But I did not understand what variations you refer to.

6. Dear Igor and Gil,

There is at least one additional face vector that satisfies the 3-valent face “vector” condition which can not be realized for an infinite number of values of the number of hexagons. This is given by the result in section 13.4, pg. 271, of Grunbaum’s convex polytopes.

Another interesting example is that one cannot have 3-valent 3-polytopes with faces which are only triangles and k-gons when k is bigger than 10. While Eberhard’s theorem says there are values for a number of hexagons that work for these polyhedra I am not exactly sure what the admissible set for the number of hexagons is (for fixed k).

Gil: Thanks for calling to my attention the Riley-Thurston paper. This reminds me of an interesting conjecture of Grunbaum’s inspired by the lovely theorem of David Barnette:

A planar 3-connected graph G has a spanning tree of maximal valence 3.

I think Grunbaum’s conjecture is still open, namely, that given a 3-polytopal graph G and its dual graph, one can find a pair of “dual trees” each of which has maximal valence 3. (The tree in one of the two dual polytopes giving rise to the other tree.)