Plane triangulations without large 2-trees

doi:10.26493/1855-3974.3066.5bf

Plane triangulations without large 2-trees

2026-01-01

0

PRE

AI

DOI：10.26493/1855-3974.3066.5bf

原文链接

原文求助

摘要

En 中文

1995年，蔡磊珍询问每个平面三角剖分是否具有生成2-树。这一问题最近由Bickle给予了否定回答。他给出了一个38个顶点的平面三角剖分，其中每个包含于其中的2-树至少缺少一个顶点。我们给出了一个29个顶点的更小例子，并证明对于每个c > 0，存在平面三角剖分P = (V, E)，使得每个作为P的子图的2-树包含的顶点数少于c|V|。我们还通过证明每个平面三角剖分P = (V, E)包含至少log₂(|V| - 1) + 4 - log₂3个顶点的2-树，给出了平面三角剖分中最大2-树大小的下界。最后，我们基于Jackson和Yu的分解树给出了结构准则，以确保平面三角剖分中生成2-树的存在性。这些结果通过利用2-树与哈密顿回路以及平面三角剖分（无分离三角形）的对偶中诱导树之间的密切关系来证明。

Keyword:

2-tree

triangulation

Hamiltonian cycle

Yutsis partition

Plane triangulations without large 2-trees

摘要

期刊

机构

引用论文