Minimal triangulations on orientable surfaces
Minimal triangulations on orientable surfaces
复制标题
可定向表面上的最小三角剖分
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
G. Ringel
中科院分区：
文献类型：
--
作者：
M. Jungerman;G. Ringel
设S是紧化的2流形。如果多面体的每个面都是一个有3个不同顶点的三角形，并且任意两个不同三角形的交点要么是空的，要么是一个顶点，要么是一个边（包括两个顶点），那么多面体就被称为三角剖分。如果三角形的数量最小，则S上的三角剖分称为最小。例如，四面体是球面的最小三角剖分，而众所周知的环面7个顶点的完全图嵌入是环面的最小三角剖分。设~(S)为S的最小三角剖分中三角形的个数。1950年，在波恩大学的一次研讨会上，E. Peschl提到了确定每个曲面S的~(S)的问题。1955年O. Ringel[9]给出了S不可定向的完全解。本文给出了该问题可定向部分的完整解。证明了~属可定向曲面Sp的6（Sv）的一个公式。这个公式的证明是一个本质上类似的问题，在复杂性上至少等同于确定完全图K n的属的问题。在这两个问题中，必须展示完全或接近完全图的三角形嵌入（其中一些边缺失）。在Kn的属问题中，为了获得缺失的边，必须添加句柄。在确定6（S~）的问题中，情况正好相反：必须找到减去手柄的方法，以便在保留三角剖分的同时去除边缘。
Let S be a compact 2-manifold. A polyhedron on S is called a triangulation if each face of the polyhedron is a triangle with 3 distinct vertices and the intersection of any two distinct triangles is either empty, a single vertex or a single edge (including the two vertices). A triangulation on S is called minimal if the number of triangles is minimal. For instance the tetrahedron is a minimal triangulation of the sphere and the well known embedding of the complete graph with 7 vertices in the torus is a minimal triangulation of the torus. Let ~(S) be the number of triangles in a minimal triangulation of S. In 1950 at a seminar at the University of Bonn, E. Peschl mentioned the problem of determining ~(S) for each surface S. The question m a y well be older than this. In 1955 O. Ringel [9] gave a complete solution if S is non-orientable. In this paper we present a complete solution of the orientable par t of the problem. We prove a formula for 6(Sv) for the orientable surface Sp of genus ~. The proof of the formula is a problem similar in nature and a t least equivalent in complexity to the problem of determining the genus of the complete graph K n. In both problems one must exhibit triangular embeddings of graphs which are complete or nearly complete (where some edges are missing). In the genus problem for Kn one has to add handles in order to gain the missing edges. In the problem of determining 6(S~) the situation is reversed: one must find ways to subtract handles in order to remove edges, while preserving the triangulation.