Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B
Volume 157, Issue -, Pages 235-262Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2022.06.003
Keywords
Surface; Quadrangular embedding; Minimal quadrangulation
Categories
Funding
- Simons Foundation [359516]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available