  Hartsfield and Ringel constructed orientable quadrangular embeddings of the
complete graph $K_n$ for $n\equiv 5 \pmod 8$, and nonorientable ones for $n \ge
9$ and $n\equiv 1 \pmod 4$. These provide minimal quadrangulations of their
underlying surfaces. We extend these results to determine, for every complete
graph $K_n$, $n \ge 4$, the minimum genus, both orientable and nonorientable,
for the surface in which $K_n$ has an embedding with all faces of degree at
least $4$, and also for the surface in which $K_n$ has an embedding with all
faces of even degree. These last embeddings provide sharpness examples for a
result of Hutchinson bounding the chromatic number of graphs embedded with all
faces of even degree, completing the proof of the Even Map Color Theorem. We
also show that if a connected simple graph $G$ has a perfect matching and a
cycle then the lexicographic product $G[K_4]$ has orientable and nonorientable
quadrangular embeddings; this provides new examples of minimal
quadrangulations.
