Diagonal flips in plane graphs with triangular and quadrangular faces
Diagonal flips in plane graphs with triangular and quadrangular faces
复制标题
具有三角形和四边形面的平面图中的对角线翻转
DOI：
10.1016/j.dam.2020.01.007
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Nakamoto and S. Negami20
中科院分区：
文献类型：
--
作者：
N. Matsumoto;A. Nakamoto and S. Negami20
三角四边形是一个连通的简单平面图形，每个面都是三角形或四边形。最近，Aichholzer等人（2014）证明了任意两个有n个顶点和m≥2个三角形面的三四边形都可以通过一系列局部变换（称为对角翻转）相互转换，并且他们的算法保证最多O （n 2）次对角翻转是足够的。本文将它们的上界改进为O (n)，并证明了估计的线性阶是最好的。
A tri-quadrangulation is a connected simple plane graph with each face either triangular or quadrangular. Recently, Aichholzer et al.(2014) proved that any two tri-quadrangulations with n vertices and m≥ 2 triangular faces can be transformed into each other by a sequence of local transformations, called a diagonal flip, and their algorithm guarantees that at most O (n 2) diagonal flips are sufficient. In this paper, we improve their upper bound to O (n), and prove that the linear order of the estimation is best possible.