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

Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color.

Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings.

My first question is whether for a genus $g$ and matching number $M$, is there a way to quickly check such a bipartite graph on $2n$ vertices exists? My second question is whether there is an algorithm to construct such a graph quickly if such a graph exists?

share|cite|improve this question

The graph genus problem is NP-hard, so I don't know if this can really be done, at least we don't expect anything to be done quickly.

share|cite|improve this answer
I guess the basic reference is Thomassen's paper "The graph genus problem is NP-complete." MR1022112 – François G. Dorais Jul 17 '11 at 4:59

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.