GRAPHS ON SURFACES JÜRGEN BOKOWSKI
For the former longstanding four colour problem: "are the countries of each given map on the sphere colourable with 4 colours?" we have an affirmative answer since 1977 due to Appel and Haaken. In this article we look at the generalization of that problem to other surfaces, i.e. either a sphere with a finite number n of handles attached to it, or a sphere in which a finite number of circular holes have been filled with a Möbius strip each. Again we can ask: "what is the minimal number n of colours for such a surface such that any given map on the surface can be coloured with n colours?" We find the classical contributions to this topic in Gerhard Ringel’s book about the map colour theorem from 1974. It starts as follows: "In 1890 P.J.Heawood published a formula which he called the Map Colour Theorem. But he forgot to prove it. Therefore the world of mathematicians called it the Heawood Conjecture. In 1968 the formula was proven and therefore again called the Map Colour Theorem." This proof is due to Ringel and Youngs and coworkers. The problem is essentially that of finding for a given surface of genus g the smallest n for which the complete graph with n vertices can be embedded on that surface without self intersections.
Ringel himself tried to find a model in the orientable genus 6 case in which the complete graph with 12 vertices can be embedded on the surface but he did not succeed. Try to start with the pottery model above and draw the 66 connecting curves on it without selfintersections. The following model with a tetrahedral symmetry (corresponding to the proper rigid motions of the tetrahedron) shows such a solution in the highest symmetrical case. See also the website of Carlo Séquin for such a model.
Whereas this solution is interesting in its own right, such a model has its interest in connection with a longstanding problem concerning the realization of triangulated 2manifolds. Grünbaum has asked the following question: does every oriented triangulated 2manifold (a sphere with g handles) have a polyhedral embedding in 3dimensional Euclidean space without intersecting triangles? It has turned out that another combinatorial version of the complete graph with 12 vertices on an orientable surface of genus 6 plays an essential role as a counter example for that problem. The symmetry in that case is that of a planar regular triangle. The surface can be seen in the next figure. We have a rotational symmetry of order 3 and when putting the model upside down, we arrive at the same model again. Whereas the surface is easy to understand, a possible shape for the complete graph with 12 vertices on that surface is more difficult to find.
The following picture (the central part) shows the complete graph with 12 vertices on such a surface. This time the surface is more difficult to detect. There is a top triangle and a bottom one with adjacent 3 triangles each. 6 triangles form a cylindrical central shape. The next topological triangles (with curves instead of line segments) are part of the handles. Because of the symmetry they have to be inserted 6 times. Some of the boundary curves occur only 3 times because of the upside down symmetry. People still find it difficult to understand the shape of that model. In order to find the result that the corresponding map has no polyhedral realization, the theory of oriented matroids has been applied, see the article by Bokowski and Guedes de Oliveira. A certain flavour of the theory of oriented matroids with its wide range of applications can be guessed when we look at the possible representations of a matrix. The following (5x3)matrix can represent 5 vectors in 3dimensional Euclidean space, or 5 central planes in that space. It can also describe 5 great circles on a 2sphere or 5 points on that sphere. A tangent plane attached to the sphere tells us that we can reinterpret the matrix as a point configuration within that tangent plane or as a line configuration. But there are many more interpretations, the rows of the matrix generate a vector space, this in turn defines an orthogonal vector space etc.
When we think about the great circle representation of a matrix, we can understand that the following models show the vertex figure of an icosahedron on the one hand and Pappos’ configuration in the projective plane on the other.
This great circle representation of a matrix is close to the topological
generalization of the equivalence class concept for matrices. We study
simple central symmetric closed curves on the 2sphere like in the two
following examples.
These models together with the following pottery model shows the embryonic stage of a recent discovery of the author with T. Pisanski. Oriented matroids of rank 3 and complete graph embeddings on surfaces can be viewed as closely linked, see the cited article by Bokowski and Pisanski.
References Appel, H., Haaken, W. (1977) Every planar map is four colourable, Illinois J. Math., 21, 429490. Bokowski, J.: (1991) On the geometric flat embedding of abstract complexes with symmetries, In: Hofmann, K. H. and Wille, R., eds., Symmetry of Discrete Mathematical Structures and their Symmetry Groups: A Collection of Essays, Research and Exposition in Mathematics, 15, Berlin: Heldermann, 148, Bokowski, J. and Guedes de Oliveira, A. (2000) On the generation of oriented matroids, Discrete and Computational Geometry, 24, 197208. Bokowski, J. and Pisanski, T. (2001) Oriented matroids and complete graph embeddings on surfaces, J. Comb. Theory, Series A, submitted. Bokowski, J. (to appear) Computational Oriented Matroids, Cambridge: Cambridge University Press. Ringel, G. (1974) Map Color Theorem, Berlin: Springer.
Additional note: Möbius's torus and its dual, the Heawood map are no regular maps in the strongest sense.
