TY - JOUR

T1 - Embedding digraphs on orientable surfaces

AU - Bonnington, C. Paul

AU - Conder, Marston

AU - Morton, Margaret

AU - McKenna, Patricia

PY - 2002/1/1

Y1 - 2002/1/1

N2 - We consider a notion of embedding digraphs on orientable surfaces, applicable to digraphs in which the indegree equals the outdegree for every vertex, i.e., Eulerian digraphs. This idea has been considered before in the context of compatible Euler tours or orthogonal A-trails by Andersen and by Bouchet. This prior work has mostly been limited to embeddings of Eulerian digraphs on predetermined surfaces and to digraphs with underlying graphs of maximum degree at most 4. In this paper, a foundation is laid for the study of all Eulerian digraphs embeddings. Results are proved which are analogous to those fundamental to the theory of undirected graph embeddings, such as Duke's theorem [5], and an infinite family of digraphs which demonstrates that the genus range for an embeddable digraph can be any nonnegative integer given. We show that it is possible to have genus range equal to one, with arbitrarily large minimum genus, unlike in the undirected case. The difference between the minimum genera of a digraph and its underlying graph is considered, as is the difference between the maximum genera. We say that a digraph is upper-embeddable if it can be embedded with two or three regions and prove that every regular tournament is upper-embeddable.

AB - We consider a notion of embedding digraphs on orientable surfaces, applicable to digraphs in which the indegree equals the outdegree for every vertex, i.e., Eulerian digraphs. This idea has been considered before in the context of compatible Euler tours or orthogonal A-trails by Andersen and by Bouchet. This prior work has mostly been limited to embeddings of Eulerian digraphs on predetermined surfaces and to digraphs with underlying graphs of maximum degree at most 4. In this paper, a foundation is laid for the study of all Eulerian digraphs embeddings. Results are proved which are analogous to those fundamental to the theory of undirected graph embeddings, such as Duke's theorem [5], and an infinite family of digraphs which demonstrates that the genus range for an embeddable digraph can be any nonnegative integer given. We show that it is possible to have genus range equal to one, with arbitrarily large minimum genus, unlike in the undirected case. The difference between the minimum genera of a digraph and its underlying graph is considered, as is the difference between the maximum genera. We say that a digraph is upper-embeddable if it can be embedded with two or three regions and prove that every regular tournament is upper-embeddable.

UR - http://www.scopus.com/inward/record.url?scp=0036267148&partnerID=8YFLogxK

U2 - 10.1006/jctb.2001.2085

DO - 10.1006/jctb.2001.2085

M3 - Article

AN - SCOPUS:0036267148

VL - 85

SP - 1

EP - 20

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

IS - 1

ER -