Enumeration of digraph embeddings

A cellular embedding of an Eulerian digraph DD into a closed surface is said to be directed   if the boundary of each face is a directed closed walk in DD. The directed genus polynomial   of an Eulerian digraph DD is the polynomial ΓD(x)=∑h≥0gh(D)xh where gh(D)gh(D) is the number of directed embeddings into the orientable surface ShSh, of genus hh, for h=0,1,…h=0,1,…. The sequence {gh(D)∣h≥0}{gh(D)∣h≥0}, which is called the directed genus distribution   of the digraph DD, is known for very few classes of graphs, compared to the genus distribution of a graph. This paper introduces a variety of methods for calculating the directed genus distributions of Eulerian digraphs. We use them to derive an explicit formula for the directed genus distribution of any 4-regular outerplanar digraph. We show that the directed genus distribution of such a digraph is determined by the red–blue star decompositions of the characteristic tree for an outerplanar embedding. The directed genus distribution of a 4-regular outerplanar digraph is proved to be log-concave, which is consistent with an affirmative answer to a question of Bonnington et al. (2002). Indeed, the corresponding genus polynomial is real-rooted. We introduce Eulerian splitting at a vertex of a digraph, and we prove a splitting theorem for digraph embedding distributions that is analogous to the splitting theorem for (undirected) graph embedding distributions. This new splitting theorem allows conversion of the enumeration of embeddings of a digraph with vertex degrees larger than 4 into a problem of enumerating the embeddings of some 4-regular digraphs.