I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this problem been studied before?
That is given a genus $g$ bipartite graph, provide an explicit algorithm that can embed the graph in a non-intersecting manner on to a real surface with $g$ handles.
Is there any notion of equivalence of embeddings of graphs on surfaces? If so, given a genus $g$ graph, in how many non-equivalent ways can one do the embedding?