Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

1 Answer 1

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|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.