  This paper considers *-graphs in which all vertices have degree 4 or 6, and
studies the question of calculating the genus of orientable 2-surfaces into
which such graphs may be embedded. A *-graph is a graph endowed with a formal
adjacency structure on the half-edges around each vertex, and an embedding of a
*-graph is an embedding under which the formal adjacency relation on half-edges
corresponds to the adjacency relation induced by the embedding. *-graphs are a
natural generalization of four-valent framed graphs, which are four-valent
graphs with an opposite half-edge structure. In [5], the question of whether a
four-valent framed graph admits a Z2-homologically trivial embedding into a
given surface was shown to be equivalent to a problem on matrices. We show that
a similar result holds for *-graphs in which all vertices have degree 4 or 6.
This gives an algorithm in quadratic time to determine whether a *-graph admits
an embedding into the plane.
