Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Packing Plane Perfec ...
Article

Packing Plane Perfect Matchings into a Point Set

Ahmad Biniaz (1), Prosenjit Bose ORCID (1), Anil Maheshwari (1), Michiel Smid (1)
(1) School of Computer Science [Ottawa]
Download article
Open on HAL
Imported on
January 14, 2015
Published on
September 14, 2015
Last modified on
March 31, 2025
Volume 17
vol. 17:2
Graph Theory
DOI
10.46298/dmtcs.2132
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
1011
Views
2028
Downloads

Packing Plane Perfect Matchings into a Point Set

Ahmad Biniaz (1), Prosenjit Bose ORCID (1), Anil Maheshwari (1), Michiel Smid (1)
(1) School of Computer Science [Ottawa]
Abstract
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 ⌊log<sub>2</sub>$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • geometric graph
  • packing matching
  • plane matching
Cited by

Source: OpenCitations

  • Edge-Constrained Hamiltonian Paths on a Point Set

    Lecture notes in computer science

    Authors : Todor Antić, Aleksa Džuklevski, Jiří Fiala, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian ORCID, Maria Saumell ORCID, Johannes Zink ORCID

    Journal reference : Volume , 2026, pp. 532-546

    DOI : 10.1007/978-3-032-17801-5_39
  • Crossing-Free Perfect Matchings in Wheel Point Sets

    A Journey Through Discrete Mathematics

    Authors : Andres J. Ruiz-Vargas, Emo Welzl

    Journal reference : Volume , 2017, pp. 735-764

    DOI : 10.1007/978-3-319-44479-6_30
  • Three Edge-Disjoint Plane Spanning Paths in a Point Set

    Lecture notes in computer science

    Authors : P. Kindermann ORCID, J. Kratochvíl ORCID, G. Liotta ORCID, P. Valtr ORCID

    Journal reference : Volume , 2023, pp. 323-338

    DOI : 10.1007/978-3-031-49272-3_22
Preview
Loading PDF preview...