Question

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?

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.

http://en.wikipedia.org/wiki/Graph_embedding#Computational_complexity