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 SetArticle

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

  • 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 &#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]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

1 Document citing this article

Consultation statistics

This page has been seen 506 times.
This article's PDF has been downloaded 619 times.