Why are graph imbeddings defined the way they are?

In my recent question I asked about a proof for the fact that the dual of a dual graph imbedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph imbeddings are defined using rotation systems at all.

It seems that the natural thing to do, if one is asked to precisely define a graph imbedding, is the more geometric approach of imbedding edges as simple curves on a pre-existing surface. Indeed, this is just an abstraction of what one is doing when they draw a graph on a sheet of paper. The other attractive feature of defining imbeddings this way is that it is possible to construct imbeddings where the faces are not all 2-cells, by contrast with the rotation system definition. The downside of this approach is that there are some subtleties in defining the dual graph, as this picture shows: the imbedding on the right fails to have $G^{**} = G$.

On the other hand, it really is easy to show rigorously that the dual graph construction using rotation systems has the property $G^{**} = G$ for an imbedded graph $G$. Is this why combinatorialists usually define graph imbeddings this way? Or are there deeper reasons to avoid the geometric approach?

-

1 Answer

I can think of a couple of other reasons. The first is algorithms. Many algorithmic problems become easier if we are told that the input graph is embeddable on a surface. As a trivial example: the problem of deciding if a graph is 4-colourable is NP-hard in general, but pretty damn easy when restricted to the class of planar graphs. So, that begs the question: how do we specify an embedding of a graph in a finite way? The geometric definition that you propose is an infinite beast which we can't really feed a computer. On the other hand, it is easy to tell a computer what a rotation system is.

Secondly, we don't really lose anything with this approach. That is, most of the questions about graphs that we care about don't really depend on how the edges of the graph are drawn on the surface. One can prove that up to mucking around on the surface, rotation systems really do gives us all embeddings of graphs on a surface.

Finally, while it is perfectly reasonable to define an embedding of a graph geometrically, you actually haven't said how to define the dual graph geometrically. For example, how do you propose to geometrically define the dual of a tree embedded on say a torus?

-
Thanks for your answer. The last part speaks to the major problems I was having in trying to work with embeddings defined geometrically - it seems like even giving a construction of the dual graph which has the double-duality property is a big mess. On the other hand, I still find it somewhat disappointing that in moving to the combinatorial approach, we lose the ability to do things like embed trees on tori, which seems like something we might want to do from time to time. – Nick Salter Dec 17 '10 at 20:53