# Bipartite graphs with prescribed Matching $M$ and genus $g$.

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?

-

## 1 Answer

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

-
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