Augmenting Polygons with Matchings
Alexander Pilz
Jonathan Rollin
Lena Schlipf
André Schulz
erschienen in:
Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)

We study disjoint compatible noncrossing geometric matchings of simple polygons. That is, given a simple 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 we show that such a matching with ≤ (n - 4) / 8 edges is not maximal, that is, it can be extended by another compatible matching edge. Complementing this we construct polygons with maximal matchings with n / 6 edges. 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 5.

@InProceedings{ author = {Alexander Pilz and Jonathan Rollin and Lena Schlipf and Andr{\'e} Schulz}, title = {Augmenting Polygons with Matchings}, booktitle = {36th European Workshop on Computational Geometry (EuroCG'20)}, year = {2020}, }
Jonathan Rollin | 10.05.2024