Enumeration of digraph embeddings

A cellular embedding of an Eulerian digraph D into a closed surface is said to be directed if the boundary of each face is a directed closed walk in D . The directed genus polynomial of an Eulerian digraph D is the polynomial Γ D ( x ) = ∑ h ≥ 0 g h ( D ) x h where g h ( D ) is the number of directed embeddings into the orientable surface S h , of genus h , for h = 0 , 1 , … . The sequence { g h ( D ) ∣ h ≥ 0 } , which is called the directed genus distribution of the digraph D , 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.