2015-01-01
Packing plane perfect matchings into a point set
Publication
Publication
Discrete Mathematics and Theoretical Computer Science
,
Volume 17
-
Issue 2
p. 119-
142
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.
|