ABSTRACT
The plane and the sphere are the simplest topological surfaces. The structure of planar
graphs, and algorithms for embedding graphs on the plane are well understood.Much
less is known about graph embeddings on other topological surfaces, and the struc-
ture of these graphs. We begin with the torus, the doughnut-shaped surface shown
in Figure 15.1. We imagine this surface made out of rubber, and using scissors, cut
it along the two circumferences shown in the diagram. The surface of the torus then
unfolds into a rectangle, which is indicated on the right. The opposite sides of the
rectangle labeled amust be glued together with the arrows aligned, as must the sides labeled b, in order to reconstruct the torus. We could glue the edges in the order a, then b; or else b, then a. Both represent the same torus.