Why are graph embeddings defined the way they are?

Question

In my recent question I asked about a proof for the fact that the dual of a dual graph embedding 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 embedding, is the more geometric approach of embedding 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 embeddings this way is that it is possible to construct embeddings 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 embedding 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?

Answer 1

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?