Tessellation and Visibility Representations of Maps on the Torus

The model of the torus as a parallelogram in the plane with opposite sides identified enables us to define two families of parallel lines and to tessellate the torus, then to associate to each tessellation a toroidal map with an upward drawing. It is proved that a toroidal map has a tessellation representation if and only if its universal cover is 2-connected. Those graphs that admit such an embedding in the torus are characterized. Received November 22, 1995, and in revised form May 1, 1997.