Obstructions to genus $g+1$ bipartite graph having genus $g$

Question

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, Commented Jun 7, 2011 at 18:49
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, Commented Jun 7, 2011 at 19:19
@Matthew Kahle: We have only bipartite graphs!! Any such obstruction reduces to $K_{3,3}$. — Turbo, Commented Jun 7, 2011 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, Commented Jun 8, 2011 at 1:18

karl marx · Accepted Answer · 2014-05-10 11:29:45Z

2

i have searched google for your question and i think your question is equivalent to :

for which regular bipartite graphs do there exist quadrilateral embeddings?

so i find 3 similar papers for you :

is it helpful? thank you !

answered May 10, 2014 at 11:29

community wiki

Add a comment |

1 Answer 1