2011/07/12 by Sheyn, Aviv, Tessler, Ran J.
Computer Science · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1107.2314
openalex publication_date 2011/07/12 · openalex created_date 2022/08/31 · openalex updated_date 2026/07/28
We study the following problem - How many arbitrary edges can be removed from a complete geometric graph with 2n vertices such that the resulting graph always contains a perfect non-crossing matching? We first address the case where the boundary of the convex hull of the original graph contains at most n + 1 points. In this case we show that n edges can be removed, one more than the general case. In the second part we establish a lower bound for the case where the 2n points are randomly chosen. We prove that with probability which tends to 1, one can remove any n + Θ(n/log (n)) edges but the residual graph will still contain a non-crossing perfect matching. We also discuss the upper bound for the number of arbitrary edges one must remove in order to eliminate all the non-crossing perfect matchings.