Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.

Eg: $T_{0,0}=1$, $T_{1,0}=2$, $T_{2,0}=3$, $T_{3,0}=4$

- Is there an explicit formula for $T_{n,g}$?

We clearly have $\frac n{W(n)}\leq T_{n,0}\leq 2n$ ($W(n)$ is Lambert $W$) with upper bound achievable.

- What is the fastest growing function $c(n,g)$ we can have such that $T_{n,g}=\frac n{c(n,g)}$ is possible?

$\frac n{\log_26}<T_{n,0}$ by Petrov's comment.

I think $\frac n{c'\log g}<T_{n,g}<\frac n{c''\log g}$ should be true for some fixed $c',c''>0$.