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

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

Authors: Biniaz, Ahmad and Bose, Prosenjit and Maheshwari, Anil and Smid, Michiel

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.


Source : oai:HAL:hal-01349047v1
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]


Share

Browsing statistics

This page has been seen 18 times.
This article's PDF has been downloaded 36 times.