Minimal quadrangulations of surfaces

A quadrangular embedding of a graph in a surface Sigma, also known as a quadrangulation of Sigma, is a cellular embedding in which every face is bounded by a 4-cycle. A quadrangulation of Sigma is minimal if there is no quadrangular embedding of a (simple) graph of smaller order in Sigma. In this paper we determine n(Sigma), the order of a minimal quadrangulation of a surface 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)= inverted right perpendicular (5 + root 25-16 chi(Sigma))/2inverted left perpendicular for all other surfaces 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. (C) 2022 Elsevier Inc. All rights reserved.

Automated summary

In this paper, we determine the order of a minimal quadrangulation of a surface Sigma, denoted as n(Sigma), for all types of surfaces. The calculations for n(Sigma) are provided for different surfaces using the introduced 'diagonal technique'. The general features of this method are explained.