Quadrangular embeddings of complete graphs
Wenzhong Liu, Mark N. Ellingham, Dong Ye, Xiaoya Zha · arXiv (Cornell University) · 2016
Hartsfield and Ringel proved that a complete graph $K_n$ has an orientable quadrangular embedding if $n\equiv 5 \pmod 8$, and has a nonorientable quadrangular embedding if $n \ge 9$ and $n\equiv 1 \pmod 4$. We complete the characterization of complete graphs admitting quadrangular embeddings by showing that $K_n$ has an orientable quadrilateral embedding if $n \equiv 0 \pmod 8$, and has a nonorientable quadrilateral embedding if $n \equiv 0 \pmod 4$. We also determine the order of minimal quadrangulations for some surfaces where the corresponding graphs are not complete.