  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 $\ell$ vertices of degree 0
mod 4, we can find an orientable directed embedding with a face bounded by $T$
and with at most $\ell+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.
