Maximum genus of regular graphs

This paper provides tight lower bounds on the maximum genus of a regular graph in terms of its cycle rank. The main tool is a relatively simple theorem that relates lower bounds with the existence (or non-existence) of induced subgraphs with odd cycle rank that are separated from the rest of the graph by cuts of size at most three. Lower bounds on the maximum genus are obtained by bounding from below the size of these odd subgraphs. As a special case, upper-embeddability of a class of graphs is caused by an absence of such subgraphs. A well-known theorem stating that every 4-edge-connected graph is upper-embeddable is a straightforward corollary of the employed method.