Resolving Pisanski's Conjecture

We prove Pisanski’s conjecture on quadrilateral embeddings of regular bipartite graphs. For integers $m\ge d\ge 4$ with $4\mid md$, we construct both a connected simple $d$-regular bipartite graph $G$ with $m$ vertices in each bipartition class and an orientable quadrangulation. This graph’s genus is $$\text{ga}(G)=1+\frac{m(d-4)}{4}\mathrm{.}$$ These quadrangulations attain the lower bound on the genus from Euler’s formula. We give dihedral constructions for even $m$ and a cyclic construction for every $m\ge d$ with $4\mid d$. In each case, two cyclic permutations of a connection set of size $d$ determine all of the local rotations.