2024/03/30 by Ellingham, M. N., Ellis-Monaghan, Joanna A.
#05C10 (primary) 05C45 #05C20 (secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.00325
In 1965 Edmonds showed that every eulerian graph has a bi-eulerian embedding, i.e., an embedding with exactly two faces, each bounded by an euler circuit. We refine this result by giving conditions for a graph to have a bi-eulerian embedding that is specifically orientable or nonorientable. We give connections to the maximum genus problem for directed embeddings of digraphs, in which every face is bounded by a directed circuit. Given an eulerian digraph D with all vertices of degree 2 mod 4 and a directed euler circuit T of D, we show that D has an orientable bi-eulerian directed embedding with one of the faces bounded by T; this is a maximum genus directed embedding. This result also holds when D has exactly two vertices of degree 0 mod 4, provided they are interlaced by T. More generally, if D has ℓ vertices of degree 0 mod 4, we can find an orientable directed embedding with a face bounded by T and with at most ℓ+1 other faces. We show that given an eulerian graph G and a circuit decomposition C of G, there is an nonorientable embedding of G with the elements of C bounding faces and with one additional face bounded by an euler circuit, unless every block of G is a cycle and C is the collection of cycles of G. In particular, every eulerian graph that is not edgeless or a cycle has a nonorientable bi-eulerian embedding with a given euler circuit T bounding one of the faces. Polynomial-time algorithms giving the specified embeddings are implicit in our proofs.