Section 4.4 Drawing Graphs on Other surfaces
We saw, using stereographic projection, that being able to draw a graph on the sphere is the same as being able to draw the graph on the plane. In this section we will discuss drawing graphs on other surfaces -- the torus and the Möbius strip we will discuss in detail, though similar ideas work for any surface. We need a way to represent such graphs on a piece of paper, for use in a book (or on the exam, say). Much of the material from the rest of this chapter (Kuratowski's theorem, Euler's theorem) have analogues for other surfaces, but are beyond the scope of this module.
Subsection 4.4.1 Motivation and culture: Manifolds and Surfaces
In this short subsection we are going to be slightly informal. The goal is simply to motivate this section about drawing graphs on surfaces other than the sphere, and to give a motivating problem that we will solve the next section on Euler's Theorem.
People used to think that the earth was flat, because if you can't see the whole thing, but can just look at just one little patch of it around you, it looks like a piece of \(\reals^2\text{.}\) Formally, a mathematicians say "locally homeomorphic to \(\reals^2\)" to mean that you can't tell it apart from \(\reals^2\) by just looking at a small piece of it.
To compliment the familiar earth idea of the earth being round, we give a few more shocking thought-experiment examples. The first is: how do we know the earth is round? I, personally haven't been to space, haven't been all over the world. Maybe there's a giant tunnel running from the south pole to the north pole, and the earth is really a torus (the surface of a donut or a bagel).
The idea of the earth being the surface of the torus probably seems absolutely ridiculous, but it happens "by accident" in videogames. In old games like Pacman or Asteroids, the game takes place on one computer screen, but to keep it from having edges and corners the designers made the game "wrap around" -- if anything goes off the right edge of the screen, it comes back at the corresponding spot on the left edge of the screen, and similarly anything that goes off the top of the screen comes back on the bottom of the screen.
A similar model, expanded slightly, is used in many other video games, like early ones in the Final Fantasy series, use essentially the same process to model the surface of a planet. We claim theat any of these videogame words are actually the surface of a torus. Instead of a computer screen, let's put the world on a very flexible flat sheet. To get the left and right edges to match up, we can curl the screen up into a cylinder -- going off one edge takes us around the back of the cylinder. Now, our cylinder has two circular boundaries, coming from the top and bottom of the screen, and to get these to match up we can bend our cylinder up and glue these together to make a torus.
Finally, we can step up a dimension, we generally assume that the three dimensional space we live in is \(\reals^3\text{,}\) but what evidence do we have for that? Maybe it's got some different shape, and if we could fly for untold light years in one direction we'd come back to the earth from a different direction! I can recommend Janna Levin's popular science book / memoir "How the Universe got its Spots" for an account of how physicists studied whether patterns in the cosmic microwave background radiation could have been created by the universe being a shape other than \(\reals^3\text{.}\)
That discussion may feel out of place; its purpose was to motivate the following definition, which we will then apply to graph theory:
Definition 4.4.1.
An \(n\)-dimensional manifold is a space that is locally homeomorphic to \(\reals^2\text{.}\) A surface is a two dimensional manifold.
Subsection 4.4.2 Graphs on the Torus
The torus is another word for the surface of a donut. There are some graphs that can't be on drawn on the sphere, but can be drawn on a torus. But we need a way to represent drawing graphs on the torus just using a normal sheet of paper -- it would be awkward and impractical to hand every student an innertube or a donut at the exam to hand in with their papers.
We will do this by copying the videogame worlds we saw in the introduction. Draw a square to represent the videogame screen, and then draw the graph inside the square, with the added proviso that if while drawing an edge of the graph we hit the border of the square, we continue the edge at the same point of the opposite side of the square. To make clear what we're doing, it is useful to draw arrows on the edges of the square to indicate how they are being identified -- we put one arrowhead, pointing the same direction, on the left and right edges, to indicate that they are being identified, with the tip end end of one edge being marked to the tip end of the other, and the tail end being matched to the tail end of the other. We draw two arrowheads on the top and bottom edges, also pointing the same direction.
This whole process is illustrated in Figure 4.4.2, where the complete graphs on five and six vertices are drawn on the torus. We end with a few short tips and tricks for trying to draw graphs on surfaces.
The first is that it can be complicated to keep track of edges that wrap around the sides of the torus. If lots of them are wrapping around, it can be easy to lose track of which edges are connecting to which others on the opposite side. One way to make this clearer is to label the crossing point on one side letters or numbers in order, and then on the opposite side label with the letters and numbers going in the same direction as indicated by the arrow. Then you know that the edge that crosses at letter \(c\text{,}\) say, on one side, picks up at \(c\) on the other edge.
Another idea is to try to minimze the number of such crossings, and draw as much of the graph as possible in the center of the square, and only a few edges wrapping around the torus. One heuristic to follow is to work like we did with the planarity algorithm for Hamiltonian graphs, and try to draw a large cycle as a cycle in the square. Then, connect as many edges and extra vertices as possible through the centre of the cycle, and only when you've ruled that out try to wrap edges around the torus. This is the approach taken in the drawing of \(K_5\) in Figure 4.4.2; the outside house is a Hamiltonian cycle, two edges could be drawn in the center of the house, and then the remaining three edges have no choice to be drawn wrapping around the torus.
The drawing of \(K_6\) using another trick that is worth explaining. It begins with the drawing of \(K_5\) in black, and adds new stuff in red. It appears that four new vertices have been added, one at each corner of the square. But actually, when the edges are identified, the four corners of the sphere get identified into one point on the torus. (Check this by visualizing what happens if you folded the paper up!). Placing one of the vertices on this graph on the corner can be useful because then edges drawn from this vertex will not need to wrap around the sides of the square.
Subsection 4.4.3 Möbius strip
If you take a piece of paper and roll it up, identifying the two edges in the usual way, one obtains the cylinder. But if instead you identify the edges in the opposite way as usual, you one obtains a different surface called the Möbius strip. The Möbius strip is famous for only having one side. In the drawing shown below, if one of the ants walks all the way around the strip, when it returns to where it starts it will be on the opposite side of the strip. Similarly, whereas a cylinder has two boundary cirlces, the Möbius strip only has one.
The fact that the Möbius strip only has one boundary circle has the following surprising consequence, that makes a great "party trick", is to make a Möbius strip by taping up a strip of paper, and the cut it down the very middle of the strip -- you wind up not getting two pieces of paper, but just one!
To actually represent graphs drawn on the Möbius strip, we work similarly to what we did for the torus; we draw a square, and then we draw arrows on the left and right edges to indicate that these edges are drawn together. However, we have one arrow drawn up, and one arrow drawn down, to indicate that the ends of the strip are glued together with a half twist. Since the top and bottom of the Möbius strip do not get identified together at all, we do not draw any arrows on them. Then, if an edge goes off one end the Möbius strip near the top, it comes back on the opposite end near the bottom, and vice versa.
Finally, we explain some heuristics about drawing graphs on surfaces, with reference drawings of \(K_{3,3}\) on the Möbius strip. As discussed at the end of the section of the torus, it can be useful to follow part of the reasoning used in the planarity algorithm for Hamiltonian cycles when trying to draw graphs on surfaces other than the sphere. That is, start with a large cycle in the graph -- for \(K_{3,3}\text{,}\) with \(a,b,c\) red vertices, and \(x,y,z\) the blue vertices, we will use the cycle \(axbycza\text{.}\) It may be that this is cycle is drawn in the plane as a circle, as the in the left hand example; then we try to connect as many edges as possible through the centre of the circle, and then do the rest on the outside, possible wrapping around the Möbius strip.
But the Jordan Curve Theorem (that a circle has an inside and an outside) only holds for the sphere -- on other surfaces, there are always curves where this isn't true. Whether of necessity, or choice, it might be that our large cycle is drawn as one of these loops that doesn't have an inside or an outside. On the right hand side of Figure 4.4.4, we have drawn the cycle \(axbycz\) as the centre of the Möbius strip.
Finally, we note that in general for a surface, there are multiple different ways to draw curves; in Figure 4.4.5, we have drawn our chosen Hamiltonian cycle as a curve that wraps twice about the Möbius strip. What happens if you cut a physical Möbius strip along this line?
