number of ribbon structures (or punctured surfaces) on a graph

Suppose $G$ is connected undirected graph.

Does the calculation of the number of topologically distinct punctured surfaces that can arise from putting a ribbon structure on $G$ exist in the literature? Or in other words do we know how to list the number of punctures (or equivalently, the genera) of the possible surfaces from the knowledge of the valencies of the vertices of the graph?

Thanks.

-
Think Euler characteristic. – Jim Conant Apr 13 '11 at 22:17