论文标题
增强与匹配的几何图
Augmenting Geometric Graphs with Matchings
论文作者
论文摘要
我们研究了非交叉几何图及其不连接兼容的几何匹配。给定一个循环（多边形）P，我们想绘制一组成对的脱节直线边缘，在P的顶点上具有端点，以使这些新的边缘既不包含多边形的任何边缘。我们证明了NP的完整性，即确定是否有如此完美的匹配。对于任何n-vertex多边形，具有n> 3的多边形，我们表明这种匹配少于N/7边缘不是最大的，也就是说，它可以通过另一个兼容的匹配边缘扩展。我们还构建具有最大兼容匹配的多边形，具有N/7边缘，证明了该结合的紧密度。对于{0,1,2}中的每个D的drigular几何图家族，还获得了最小最大兼容匹配大小的紧密界限。最后，我们考虑了一个相关的问题。我们证明，确定非交叉几何图G是否允许一组兼容的非交叉边缘，以使G与这些边缘一起具有最低程度的第五，这是NP的完整。
We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges with endpoints on the vertices of P such that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon, with n > 3, we show that such a matching with less than n/7 edges is not maximal, that is, it can be extended by another compatible matching edge. We also construct polygons with maximal compatible matchings with n/7 edges, demonstrating the tightness of this bound. Tight bounds on the size of a minimal maximal compatible matching are also obtained for the families of d-regular geometric graphs for each d in {0,1,2}. Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree five.
