论文标题
计数平面三角剖分的周期
Counting cycles in planar triangulations
论文作者
论文摘要
我们研究了平面$ n $ vertex三角元中指定长度的最小循环数量。事实证明，任何周期长度的$ 3 + \ max \ {{{\ rm rad}（g^*），\ lceil（\ frac {n-3} {2} {2} {2}）^{\ log_32} \ rceil \ rceil \} $ rad rad}三角剖分的双重，至少是对数，但可以按三角剖分顺序进行线性。我们还表明，存在$ o（n）$ o（n）$ o k $ cycles的平面汉密尔顿$ n $ vertex三角形，用于任何$ k \ in \ in \ {\ lceil n- \ sqrt [5] {n} \ rceil，\ rceil，\ ldots，n \} $。此外，我们证明了平面4连接的$ n $ vertex三角形包含$ω（n）$多$ k $ -cycles，每个$ k \ in \ in \ {3，\ ldots，n \} $，以及在某些其他条件下，它们包含$ω（n^2）$ k $ $ $ $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k k $ k k a $ k $ k k a $ k k k a $ k k k a $ k k k k k a $ k k k a $ k k k a n more n of n n $ k k k。
We investigate the minimum number of cycles of specified lengths in planar $n$-vertex triangulations $G$. It is proven that this number is $Ω(n)$ for any cycle length at most $3 + \max \{ {\rm rad}(G^*), \lceil (\frac{n-3}{2})^{\log_32} \rceil \}$, where ${\rm rad}(G^*)$ denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian $n$-vertex triangulations containing $O(n)$ many $k$-cycles for any $k \in \{ \lceil n - \sqrt[5]{n} \rceil, \ldots, n \}$. Furthermore, we prove that planar 4-connected $n$-vertex triangulations contain $Ω(n)$ many $k$-cycles for every $k \in \{ 3, \ldots, n \}$, and that, under certain additional conditions, they contain $Ω(n^2)$ $k$-cycles for many values of $k$, including $n$.
