MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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 !

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.