Packing plane perfect matchings into a point set
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.
|Keywords||Geometric graph, Packing matching, Plane matching|
|Journal||Discrete Mathematics and Theoretical Computer Science|
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.