Introduction

A ubiquitous question in topological graph theory is whether a given graph can be embedded in a given surface, a question that readily extends to the problem of counting the number of different embeddings of that graph into that surface. (A contrasting classical problem with its origins in geometry asks, for a fixed surface, how many different maps there are onto that surface, where what varies is the graph that serves as the 1-skeleton.) This chapter explores the programme introduced by Gross and Furst [11] of constructing surface-by-surface inventories of the embeddings of a fixed graph into not just one surface, but every surface, and gives the related theory.

All embeddings are taken to be cellular, except where it is clear from context that non-cellular embeddings are under consideration. Two cellular embeddings are considered to be the same if their rotation systems are combinatorially equivalent (see Chapter 1).

Given a graph G and an orientable surface Sh, the number of embeddings of G in Sh is the number gh(G) of rotation systems for G that induce a cellular embedding in Sh. The orientable genus range of a graph G is the set of integers h for which gh(G) > 0.