# Obstructions to genus $g+1$ bipartite graph having 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 \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?

-
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. –  Turbo 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}$. –  Turbo 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

for which regular bipartite graphs do there exist quadrilateral embeddings?

so i find 3 similar papers for you :

1. http://www.ams.org/journals/tran/1970-151-02/S0002-9947-1970-0281653-3/

2. http://lib.gen.in/16bbcefe972e05a1cb422e8ff3b9bc73.pdf

3. www.sciencedirect.com/science/article/pii/0012365X89901702

is it helpful? thank you !

-