Embedding digraphs on orientable surfaces (Q1850600): Difference between revisions

The topic of embeddings of directed graphs considered in this article is a restriction of the problem of (general) graph embeddings on orientable surfaces. The digraphs under consideration must be Eulerian, and their embeddings are to be 2-cell embeddings on orientable surfaces satisfying the additional property that the arcs on the boundary of every region must all point in the same direction (i.e., the boundary of every region is an oriented circuit of the underlying digraph). The authors investigate several analogs of the classical graph embedding problems, and obtain a surprising number of interesting general results. They show, for example, that under these restrictions, the genus list (the list of all possible genera of surfaces admitting an embedding) of any digraph is an unbroken interval of integers, and characterize regular digraphs \(D\) of in- and out-degree 2 that admit an embedding with exactly two regions (if and only if \(D\) admits two Euler circuits with no common pair of consecutive arcs). They also construct a family of digraphs with an increasing minimal number of regions, a family of digraphs with an unbounded genus range, and a family of digraphs that shows that the minimum genus can be arbitrarily large while the embedding range remains 1 (a result that differs from the case of general graph embeddings). They also show that both the minimum and maximum genus of a digraph may be arbitrarily different from the minimum and maximum genus of the corresponding underlying graph. In their final result, the authors determine the maximum genus of every regular tournament by showing that every regular tournament can be embedded with two or three regions.