Packing Plane Perfect Matchings into a Point SetArticleAuthors: Ahmad Biniaz
1; Prosenjit Bose
1; Anil Maheshwari
1; Michiel Smid
1
NULL##0000-0002-8906-0573##NULL##NULL
Ahmad Biniaz;Prosenjit Bose;Anil Maheshwari;Michiel Smid
- 1 School of Computer Science [Ottawa]
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.
Volume: Vol. 17 no.2
Section: Graph Theory
Published on: September 15, 2015
Imported on: January 15, 2015
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] geometric graph, packing matching, plane matching
Funding:
Source : OpenAIRE Graph- Funder: Natural Sciences and Engineering Research Council of Canada