Combinatorial Structure of Faces in Triangulations on Surfaces
Oleg Veniaminovich Borodin, Anna O. Ivanova · Siberian Mathematical Journal · 2022
The degree $ d(x) $ of a vertex or face $ x $ in a graph $ G $ on the plane or other orientable surface is the number of incident edges. A face $ f=v_{1}\ldots v_{d(f)} $ is of type $ (k_{1},k_{2},\dots) $ if $ d(v_{i})\leq k_{i} $ whenever $ 1\leq i\leq d(f) $ . We denote the minimum vertex-degree of $ G $ by $ \delta $ . The purpose of our paper is to prove that every triangulation with $ \delta\geq 4 $ of the torus, as well as of large enough such a triangulation of any fixed orientable surface of higher genus has a face of one of the types $ (4,4,\infty) $ , $ (4,6,12) $ , $ (4,8,8) $ , $ (5,5,8) $ , $ (5,6,7) $ , or $ (6,6,6) $ , where all parameters are best possible.