## Ahmad Biniaz ; Prosenjit Bose ; Anil Maheshwari ; Michiel Smid - Packing Plane Perfect Matchings into a Point Set

dmtcs:2132 - Discrete Mathematics & Theoretical Computer Science, September 15, 2015, Vol. 17 no.2 - https://doi.org/10.46298/dmtcs.2132
Packing Plane Perfect Matchings into a Point Set

Authors: Ahmad Biniaz ; Prosenjit Bose ; Anil Maheshwari ; Michiel Smid

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 &#x230A;log<sub>2</sub>$n$&#x230B;$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.

Volume: Vol. 17 no.2
Section: Graph Theory
Published on: September 15, 2015
Submitted on: January 15, 2015
Keywords: packing matching,geometric graph,plane matching,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]