Construction of graph embeddings with non-intersecting edges
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.