Bi-eulerian embeddings of graphs and digraphs

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 a 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.