A note on strong embeddings of maximal planar graphs on non-orientable surfaces (Q5943373)

An embedding of a graph in a closed surface is said to be a closed 2-cell embedding if every face is a disk bounded by a simple circuit of the graph. In this paper, it is shown that every maximal planar graph of order \(n\) admits a strong 2-cell embedding in every nonorientable surface with genus at most \((n-2)/2\). The dual graph of such an embedding of genus \(g\) can be obtained from the dual graph \(G^*\) in the plane by applying the \(Y\Delta\) transformation on the set of \(g\) pairwise nonadjacent vertices of \(G^*\). This implies that strong 2-cell embeddings with planar dual graph exist for \(1 \leq g \leq (n-2)/2\).