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 ORCID-iD; 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]

    Share

    Consultation statistics

    This page has been seen 253 times.
    This article's PDF has been downloaded 393 times.