Irreducible Triangulations of Surfaces
Irreducible Triangulations of Surfaces
复制标题
曲面的不可约三角剖分
DOI：
10.1006/jctb.1996.0064
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
Zhicheng Gao;R. Richter;P. Seymour
本文证明了，对于任意曲面7和任意k，至多有有限多个7的三角剖分，使得每条边都在一个长度为k的不可压缩循环中，并且不在更短的不可压缩循环中。这样的三角剖分是k-不可约的。这等价于对于任意曲面7和任意k，在7中至多有有限多个嵌入是具有代表性k的次极小的。这最后一个事实可以从一个定理(瓦格纳猜想的变体)推导出来，即嵌入曲面的图的顶点和边由良拟序标号，在关于标号的抽象子式下形成良拟序图。然而，这一证明非常复杂，并不具有建设性。最近，几篇文章讨论了证明至多有有限多个3-不可约三角剖分[BE，GRT，NO]的问题。Malnic和Mohar[MM]证明了可定向曲面至多有有限多个4-不可约三角剖分。Malnic$和Nedela[MN]给出了7的k-不可约三角剖分的个数对所有k和所有7都是有限的第一个初等证明。Gao等[GRT]有一个非常简单的证明：任何具有欧拉特征2&！的曲面(可定向的或不可定向的)的3-不可约三角剖分中至多有c！4个顶点，而Nakamota和Ota[no]证明(用类似的简单证明)实际上至多有c！三角剖分中的顶点。在本文中，我们给出了Malnic定理和Nedela定理的一个非常简短、简单的证明。此外，我们给出了形式ck！2的一个显式估计。
In this note we show that, for any surface 7 and any k, there are at most finitely many triangulations of 7 such that each edge is in a noncontractible cycle of length k and is in no shorter noncontractible cycle. Such a triangulation is k-irreducible. This is equivalent to the statement that for any surface 7 and any k, there are at most finitely many embeddings in 7 that are minor minimal with representativity k. This last fact can be derived from a theorem (a variant of Wagner's conjecture) that graphs embedded in a surface, with vertices and edges labelled from a well-quasi-order, form a well-quasi-order under abstract minors respecting the labels. However, this proof is very complicated and is not constructive. Thus, it is desirable to have an elementary proof of this particular consequence.Recently, several papers have dealt with the problem of showing that there are at most finitely many 3-irreducible triangulations [BE, GRT, NO]. Malnic $ and Mohar [MM] prove that there are at most finitely many 4-irreducible triangulations of an orientable surface. Malnic $ and Nedela [MN] have given the first elementary proof that the number of k-irreducible triangulations of 7 is finite for all k and all 7. Gao et al.[GRT] have a very simple proof that there are at most c! 4 vertices in a 3-irreducible triangulation of any surface (orientable or not) with Euler characteristic 2&!, while Nakamota and Ota [NO] show (with a similar simple proof) that in fact there are at most c! vertices in such a triangulation. In this note, we give a very short, simple proof of the Malnic $ and Nedela theorem. Moreover, we give an explicit estimate of the form ck! 2 on the