  This paper considers *-graphs in which all vertices have degree 4 or 6, and
studies the question of calculating the genus of nonorientable surfaces into
which such graphs may be embedded. In a previous paper by the authors, the
problem of calculating whether a given *-graph in which all vertices have
degree 4 or 6 admits a Z2-homologically trivial embedding into a given
orientable surface was shown to be equivalent to a problem on matrices. Here we
extend those results to nonorientable surfaces. The embeddability condition
that we obtain yields quadratic-time algorithms to determine whether a *-graph
with all vertices of degree 4 or 6 admits a Z2-homologically trivial embedding
into the projective plane or into the Klein bottle.
