A Graph-Coloring Result and Its Consequences For Polygon-Guarding Problems
A Graph-Coloring Result and Its Consequences For Polygon-Guarding Problems
复制标题
多边形保护问题的图形着色结果及其后果
DOI：
10.1137/s0895480194265611
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
K. Kriegel
中科院分区：
文献类型：
--
作者：
Frank Hoffmann;K. Kriegel
证明了如下图着色结果：设G是2连通二部平面图。然后我们可以三角化$G$以这样一种方式，得到的图是3-着色的。时间复杂度为O（n^2）。这一结果意味着几个新的上界多边形守卫问题，包括第一个非平凡的上界的直线监狱院子问题。(1)$\lfloor{n}/{3}\rfloor$顶点防护足以监视带孔的直线多边形的内部。(2)$\lfloor{5 n}/{12}\rfloor +3 $顶点后卫（$\lfloor{n+4}/{3}\rfloor $控球后卫）足以同时监视直线多边形的内部和外部。此外，给出了直线型监狱庭院问题的$\lfloor{5 n}/{16}\rfloor$顶点守卫的一个新下界，并证明了该下界对于正交凸多边形类是渐近紧的.
The following graph-coloring result is proved: let $G$ be a 2-connected, bipartite, and plane graph. Then one can triangulate $G$ in such a way that the resulting graph is 3-colorable. Such a triangulation can be computed in $O(n^2)$ time. This result implies several new upper bounds for polygon guarding problems, including the first nontrivial upper bound for the rectilinear prison yard problem. (1) $\lfloor{n}/{3}\rfloor$ vertex guards are sufficient to watch the interior of a rectilinear polygon with holes. (2) $\lfloor{5n}/{12}\rfloor +3$ vertex guards ($\lfloor{n+4}/{3}\rfloor $ point guards) are sufficient to simultaneously watch both the interior and exterior of a rectilinear polygon. Moreover, a new lower bound of $\lfloor{5n}/{16}\rfloor$ vertex guards for the rectilinear prison yard problem is shown and proved to be asymptotically tight for the class of orthoconvex polygons.