Construction of graph embeddings with non-intersecting edges 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?
There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g.
See this paper.

Having a bipartite graph does not help. From any graph we can obtain a bipartite version by subdividing each edge once. The embeddability of the new graph and the original one is the same.