Given a set P of n points in the plane, where n is even, we consider the following question: How many plane perfect matchings can be packed into P? For points in general position we prove the lower bound of [log2 n] - 1. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.

Additional Metadata
Keywords Geometric graph, Packing matching, Plane matching
Journal Discrete Mathematics and Theoretical Computer Science
Citation
Biniaz, A. (Ahmad), Bose, P, Maheshwari, A, & Smid, M. (2015). Packing plane perfect matchings into a point set. Discrete Mathematics and Theoretical Computer Science, 17(2), 119–142.