论文标题
守卫四边形和边缘的三角形
Guarding Quadrangulations and Stacked Triangulations with Edges
论文作者
论文摘要
令$ g =（v，e）$为平面图。如果至少一个来自$ \ {v，w \} $的顶点在$ f $的边界上，则$ g $的面孔$ f $由e $ in e $的边缘$ vw \守卫。对于平面图类$ \ MATHCAL {G} $，我们要求在$ \ MATHCAL {G} $中守护任何$ n $ vertex Graph所需的最小边缘。我们证明，$ \ lfloor n/3 \ rfloor $边缘始终足以进行四边形，并在需要$ \ lfloor（n-2）/4 \ rfloor $ edges的地方进行建筑。对于$ 2 $ - 定义的四边形，我们将其改进到$ \ lfloor n/4 \ rfloor $边缘的紧密上限。我们进一步证明，$ \ lfloor 2n/7 \ rfloor $边缘始终足以用于堆叠的三角形（这是$ 3 $ depegenate Triangulations），并表明这是最多可以达到一个小的增态常数。
Let $G = (V,E)$ be a plane graph. A face $f$ of $G$ is guarded by an edge $vw \in E$ if at least one vertex from $\{v,w\}$ is on the boundary of $f$. For a planar graph class $\mathcal{G}$ we ask for the minimal number of edges needed to guard all faces of any $n$-vertex graph in $\mathcal{G}$. We prove that $\lfloor n/3 \rfloor$ edges are always sufficient for quadrangulations and give a construction where $\lfloor (n-2)/4 \rfloor$ edges are necessary. For $2$-degenerate quadrangulations we improve this to a tight upper bound of $\lfloor n/4 \rfloor$ edges. We further prove that $\lfloor 2n/7 \rfloor$ edges are always sufficient for stacked triangulations (that are the $3$-degenerate triangulations) and show that this is best possible up to a small additive constant.
