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.

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]

This page has been seen 136 times.

This article's PDF has been downloaded 303 times.