Drawing Graphs on Surfaces
Arjana Žitnik · SIAM Journal on Discrete Mathematics · 1994
Every graph that is 2-cell embedded in a closed orientable surface can be drawn in some fundamental polygon of the surface so that the boundary of the polygon consists of edges and vertices of the graph; it can also be drawn so that all the vertices of the graph are inside the polygon and no edges cross the boundary of the polygon more than once. A necessary and sufficient condition is found to determine whether or not a given embedding of a graph in a surface has one or the other representation in the standard polygon of the surface, the one of the form $a_1 b_1 a_1^{ - 1} b_1^{ - 1} a_2 b_2 a_2^{ - 1} b_2^{ - 1} \cdots $. This leads to a polynomial-time algorithm, assuming that the surface is fixed.