Minimal quadrangulations of surfaces

A quadrangular embedding of a graph in a surface $\mathrm{\Sigma }$, also known as a quadrangulation of $\mathrm{\Sigma }$, is a cellular embedding in which every face is bounded by a $4$-cycle. A quadrangulation of $\mathrm{\Sigma }$ is minimal if there is no quadrangular embedding of a (simple) graph of smaller order in $\mathrm{\Sigma }$. In this paper we determine $n(\mathrm{\Sigma })$, the order of a minimal quadrangulation of a surface $\mathrm{\Sigma }$, for all surfaces, both orientable and nonorientable. Letting $S_0$ denote the sphere and $N_2$ the Klein bottle, we prove that $n(S_0)=4,n(N_2)=6$, and $n(\Sigma)=\lceil (5+\sqrt{25-16\chi(\Sigma)})/2\rceil$forallothersurfaces$\Sigma$,where$\chi(\Sigma)$ is the Euler characteristic. Our proofs use a `diagonal technique’, introduced by Hartsfield in 1994. We explain the general features of this method.