论文标题
部分可观测时空混沌系统的无模型预测
Outside-Obstacle Representations with All Vertices on the Outer Face
论文作者
论文摘要
图$ g $的障碍物表示由一组多边形障碍物和$ g $的图形作为有关障碍的可见性图：顶点映射到点和边缘到直线段，以避免每个障碍物避免所有障碍，而每个非边缘至少相交至少一个障碍。在过去的几年中，对障碍表示的调查已经进行了非常深入的调查。在这里，我们专注于外面表示（OORS），这些表示仅在图纸的外表面上使用一个障碍物。众所周知，每个外平面图都允许这样的表示。 我们通过表明每个（部分）2树都有一个OOR来增强这一结果。我们还考虑了限制版本的OORS，其中图的顶点形成凸多边形甚至常规多边形。我们表征了何时补充树的补充以及完整的图表减去一个简单的周期允许凸出。我们为所有（部分）外部路径，仙人掌图和网格构建常规OOR。
An obstacle representation of a graph $G$ consists of a set of polygonal obstacles and a drawing of $G$ as a visibility graph with respect to the obstacles: vertices are mapped to points and edges to straight-line segments such that each edge avoids all obstacles whereas each non-edge intersects at least one obstacle. Obstacle representations have been investigated quite intensely over the last few years. Here we focus on outside-obstacle representations (OORs) that use only one obstacle in the outer face of the drawing. It is known that every outerplanar graph admits such a representation. We strengthen this result by showing that every (partial) 2-tree has an OOR. We also consider restricted versions of OORs where the vertices of the graph form a convex polygon or even a regular polygon. We characterize when the complement of a tree and when a complete graph minus a simple cycle admits a convex OOR. We construct regular OORs for all (partial) outerpaths, cactus graphs, and grids.
