×

Directed embeddings of 2-regular diplanar digraphs on surfaces of low Euler genus. (English) Zbl 1490.05185

The paper studies directed embeddings of \(2\)-regular, diplanar, digraphs on surfaces. The key definitions here are the following. A directed embedding of a digraph on a surface is a \(2\)-cell embedding with the property that each face is bounded by a directed cycle. A digraph is \(2\)-regular if each vertex has both indegree and outdegree two, and is diplanar if it admits a directed embedding in the sphere.
There are two main results in this paper:
1.) It gives a shorter and simpler proof of an extension of Whitney’s theorem to directed embeddings first obtained by D. Archdeacon et al. [Australas. J. Comb. 67, Part 2, 159–165 (2017; Zbl 1375.05064)]. This result states that every strongly \(2\)-edge-connected \(2\)-regular diplanar digraph admits a unique (up to homeomorphisms) directed embedding on the sphere.
2.) It gives a structural description and characterisation of the possible directed embeddings of any strongly \(2\)-edge-connected \(2\)-regular diplanar digraphs on the projective plane, on the torus, and on the Klein bottle. In particular, this allows for an estimation of the number of different such embeddings for each fixed digraph with the above properties.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C20 Directed graphs (digraphs), tournaments
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 1375.05064

References:

[1] L. D. Andersen, A. Bouchet and B. Jackson, Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus,J. Combin. Theory Ser. B66(1996), 232-246. · Zbl 0855.05047
[2] D. Archdeacon, C. P. Bonnington and B. Mohar, Embedding quartic Eulerian digraphs on the plane,Australas. J. Combin.67(2017), 159-165. · Zbl 1375.05112
[3] D. Archdeacon, M. DeVos, S. Hannie and B. Mohar, Whitney’s theorem for 2-regular planar digraphs,Australas. J. Combin.67(2017), 364-377. · Zbl 1375.05064
[4] C. P. Bonnington, M. Conder, M. Morton and P. McKenna, Embedding digraphs on orientable surfaces,J. Combin. Theory Ser. B85(2002), 1-20. · Zbl 1029.05037
[5] C. P. Bonnington, N.Hartsfield and J. ˇSir´aˇn, Obstructions to directed embeddings of Eulerian digraphs in the plane,European J. Combin.25(2004), 877- 891. · Zbl 1052.05026
[6] Y. Chen, J. L. Gross and X. Hu, Enumeration of digraph embedding,European J. Combin.36(2014), 660-678. · Zbl 1284.05136
[7] K. Enami, Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic,Discrete Math. Theor. Comput. Sci.21 (2019). · Zbl 1430.05020
[8] R. Hao, Y. Liu, T. Zhang and L. Xu, The genus distributions of 4-regular digraphs,Australas. J. Combin.43(2009), 79-90. · Zbl 1155.05314
[9] T. Johnson,Eulerian Digraph Immersion, Ph.D. Thesis, Princeton University, 2002.
[10] B. Mohar and C. Thomassen,Graphs on Surfaces, The Johns Hopskins University Press, 2001. · Zbl 0979.05002
[11] B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces,J. Comb. Theory Ser. B68(1996), 87-111. · Zbl 0856.05027
[12] B. Mohar, N. Robertson and R. P. Vitray, Planar graphs on the projective plane, Discrete Math.149(1996), 141-157. · Zbl 0849.05023
[13] W. T. Tutte, The dissection of equilateral triangles into equilateral triangles, Proc. Cambridge Philos. Soc.44(1948), 463-482. · Zbl 0030.40903
[14] H. Whitney, Congruent Graphs and the Connectivity of Graphs,Amer. J. Math. 54(1932), 150-168. · JFM 58.0609.01
[15] H. Whitney, 2-isomorphic graphs,Amer. J. Math.55(1933), 245-254 · JFM 59.1235.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.