# Bipartite Obstructions to genus $g+1$ Bipartite graph from becoming genus $g$.

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

Say I know $g \le genus(B_{n,n}) \le g+1$: What obstructions can $B_{n,n}$ have from becoming a genus $g$ graph?

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

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

-
The Robertson–Seymour theorem guarantees that embeddability in genus $n$ is characterized by a finite list of forbidden minors, but even for the torus, no such explicit list is known (while it is known 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
Could you please provide the wiki link? Thankyou. –  J.A Jun 7 '11 at 19:07
I think it is not true that the only obstruction to being planar is having a $K_{3,3}$ subgraph. First of all, the Kuratowski theorem is for minors, not subgraphs, and a bipartite graph could still have a $K_5$ minor. For example, take $K_5$ and subdivide each edge by adding a vertex in the middle. –  Matthew Kahle Jun 7 '11 at 19:19
@Matthew Kahle: We have only bipartite graphs!! Any such obstruction reduces to $K_{3,3}$. –  J.A Jun 7 '11 at 19:25
@unknown (google): The subdivided $K_5$ I described is bipartite, non-planar, and has no $K_{3,3}$ subgraphs (or minors). –  Matthew Kahle Jun 8 '11 at 1:18
show 2 more comments