Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices.

Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being a genus $g$ graph?

When $g=0$, we know that the obstructions are $k_{3,3}$ and $K_{5}$. In general, what is the number of obstructions?

For the particular case of $K_{n,n}$ what obstructions prevent it from being a genus $\lceil{\frac{(n-2)^{2}}{4}}\rceil -1$ graph?

isknown that the list has to be awfully long, Wikipedia says $\ge16000$ graphs). It is possible that being bipartite simplifies the situation, but I kind of doubt it. – Emil Jeřábek Jun 7 '11 at 18:49