Introduction ¶
This Web page presents some properties between two perfect matchings in planar straight line graphs. Below, a simple JavaScript application allows to experiment with these concepts.
1 Some basic definitions ¶
We will consider a particular form of undirected graph, where each vertex is a point in the plane, and each edge is a segment (no curve) between two points. Moreover there is no intersection. We call that a planar straight line graph (PSLG).
A matching (or independent edge set) is a set of segments such that they have no point in common (i.e. if and only if each vertex has degree at most one). In this document we consider only matchings with no intersection.
A matching is said perfect if and only if each point is an endpoint of one and only one segment (i.e. if and only if each vertex has degree one). Of course, that requires an even number of points.
A matching is said even if and only if it have a even number of segments. Else it said odd.
Now we consider two matchings on a same PSLG. Two matchings are said disjoint if and only if their have no common segment.
Two matchings are said
compatible
if and only if their union is with no intersection.
Be careful, the union is the union of two sets (concept of set theory).
And the intersection is the intersection of two segments (geometrical concept).
Let $S$ a set of $2n$ points. If we called $p_1, p_2, p_3, \dots, p_{2n}$ in increasing order of their xcoordinates (and for points with the same xcoordinate, in increasing order of their ycoordinates), the canonical perfect matching of $S$, written $N(S)$, is the perfect matching with segments $p_1$—$p_2, p_3$—$p_4, p_5$—$p_6, \dots p_{2n1}$—$p_{2n}$.
2 Transformation between two perfect matchings ¶
When two perfect matchings are not compatible, it may be possible to have a succession of perfect matchings two by two compatible, from the first one to the last one.
We call transformation between two perfect matchings a sequence of perfect matchings such that each consecutive pair of perfect matchings is compatible. More formally, with $S$ a set of points, $M$ and $M'$ two perfect matchings of $S$, a transformation between $M$ and $M'$ of length $k$ is a sequence $M = M_0, M_1, M_2, \dots, M_k = M'$ of perfect matchings of $S$ such that $\forall i \in \{0, 1, 2, \dots, k1\}: M_i$ and $M_{i+1}$ are compatible.
If moreover $\forall i \in \{0, 1, 2, \dots, k1\}: M_i$ and $M_{i+1}$ are disjoint, the transformation is called a disjoint transformation.
2.1 Lemmas ¶
Lemma ⅰ
$\forall$ perfect matching $M$,
$\forall$ line $t$ cutting an even number of segments of $M$
(such that $t$ contains no vertex),
let $H$ the halfplane determined by $t$,
let $S$ the set of vertices of $M$ in $H$,
$\exists$ perfect matching $M'$ of $S:
M$ and $M'$ are compatible
Lemma ⅱ
$\forall$ perfect matching $M$,
$\forall$ line $t$ cutting an even number of segments of $M$
(such that $t$ contains no vertex),
let halfplanes $H_1$ and $H_2$ determined by $t$,
let $S_1$ and $S_2$ sets of vertices of $M$ in $H_1$ and in $H_2$,
$\exists$ perfect matchings $M_1$ of $S_1$ and $M_2$ of $S_2:
M$ and $(M_1 \cup M_2)$ are compatible
By two applications of lemma ⅰ, there are perfect matchings $M_1$ of $S_1$ and $M_2$ of $S_2$ such that $M$ and $M_1$ are compatible, and $M$ and $M_2$ are compatible. Since $M_1$ and $M_2$ are separated, then $M_1 \cup M_2$ is also a perfect matching and $M$ and $(M_1 \cup M_2)$ are compatible.
Lemma ⅲ
$\forall S$ of $2n$ points, $\forall$ perfect matchings $M$ of $S$, $\exists$ transformation of length at most $\lceil$$\lg(n)$$\rceil$ between $M$ and $N(S)$
 Base case: $n = 1$. All perfect matchings with 2 points are canonical, so the transformation has length $0 = \lg(1)$.
 Inductive hypothesis. Assume that the lemma is true for all value less than $n$ with $n > 1$.

Inductive step.
Let a vertical line $t$ cutting the plane in two parts (left $H^l$ and right $H^r$) such that $H^l$ contains a set $S^l$ of $2\lfloor\frac{n}{2}\rfloor$ points and $H^r$ contains a set $S^r$ of $2\lceil\frac{n}{2}\rceil$ points.
Let $m$ the number of segments cut. The subset of segments in the left that no intersects with $t$ is a perfect matching, so $2\lfloor\frac{n}{2}\rfloor  m$ is even and $m$ too.
By lemma ⅱ, there is perfect matchings $M^l$ of $S^l$ and $M^r$ of $S^r$ such that $M$ and $(M^l \cup M^r)$ are compatible
By inductive hypothesis to $M^l$ and $M^r$ there are theses transformations:
$M^l = M^l_0, M^l_1, M^l_2, \dots, M^l_k = N(S^l)$
$M^r = M^r_0, M^r_1, M^r_2, \dots, M^r_k = N(S^r)$where $\lceil\lg\lfloor\frac{n}{2}\rfloor\rceil \leq \lceil\lg\lceil\frac{n}{2}\rceil\rceil \leq \lceil\lg(n)\rceil  1 = k$
$\forall i: M^l_i$ and $M^l_{i+1}$ are compatible, and $M^r_i$ and $M^r_{i+1}$ are compatible.
Let $M_i = M^l_i \cup M^r_i$. It is a perfect matching of $S$, because $M^l_i$ and $M^r_i$ are separated by $t$. And $M_i$ and $M_{i+1}$ are compatible.
$N(S) = N(S^l) \cup N(S^r) = M_k$
so $M, M_0, M_1, M_2, \dots, M_k$ is a transformation between $M$ and $N(S)$ of length $\lg(n)$
2.2 Theorem ¶
Theorem ⅳ
$\forall$ perfect matchings $M$ and $M'$, $\exists$ transformation of length at most $2 \lceil\lg(n)\rceil$ between $M$ and $M'$
Let $S$ the set of $2n$ points. By lemma ⅲ there are perfect matchings $M$ and $M'$ such that
$M' = M'_0, M'_1, M'_2, \dots, M'_{k'} = N(S)$ with $k, k' \leq \lceil\lg(n)\rceil$.
Thus $M_0, M_1, M_2, \dots, M_k = M'_{k'}, \dots, M'_2, M'_1, M'_0 = M'$ is a transformation of length at most $2 \lceil\lg(n)\rceil$.
3 Experiment by yourself ¶
3.1 Interactive application ¶
Click in the two zones to add/remove point or segment (only one segment by point and with no intersection). You can also click on one matching example to load it in the interactive zones. Wait a moment above a button to bring up a short explanation tooltip.
 :
 :
 :
3.2 Some explanations ¶
You can add or remove points one by one, but only perfect matchings are useful. Isolated points are drawing in red. To remove a point, click on it. When a point is removed, all its segment are removed.
To add a segment, click to add the first point, then click to add the second point and the segment. It is impossible to add a segment to a point that already belongs to a segment, or to add a segment that intersects with an other segment. To remove a segment (and keeping its points), click to a first point and then to the second point.
If a matching is a canonical perfect matching then it is in a blue frame.
For two consecutive matchings in the list, common segments are in orange and segments that intersects between them are in red.
By default, all segments of the immediately previous and next matchings are drawn in thin silver. An option permits to draw all segments that are in at least one matching in the list, or on the contrary to disable that and to draw only the segments of the matching.
For the matchings of the two interactive zones, some properties are displayed. Below that, some global properties between these two matchings are also displayed.
The matching of the left interactive zone is also displayed in the first position in the list. And the matching of the right interactive zone is displayed in the last position. Between them, are displayed all other perfect matchings or the intermediary perfect matchings to be a transformation.
Build all perfect matchings or build a shortest transformation are very expensive operations, so they are impossible with a lot of points. Moreover only transformations of length 2 and 3 are tried.
The upper bound given by the application for the number of possible perfect matchings is very rough. In fact it is the number of general (with possible intersection) perfect matchings.
With $n = 2k$: $\{\text{general perfect matching}\} = (n  1).(n  3).(n  5) … 5 . 3 = \frac{n!}{n.(n  2).(n  4) … 4 . 2} = \frac{n!}{2^k . k!}$.
And the Stirling’s approximation $n! \sim \sqrt{2 \pi n} (\frac{n}{e})^n$ give the approximation $\sqrt{2} (\frac{n}{e})^k$.
3.3 Sources code ¶
The interactive application was tested on Firefox 52.0 (and a little on Chromium 57.0) (requires ECMAScript/JavaScript 2015 6^{th} and modern browser).
 The online JavaScript source codes/ for this application. License GPLv3
 The complete sources of this project on Bitbucket.
 Online HTML documentation of source codes.
4 Compatible matching conjecture ¶
Compatible matching conjecture
$\forall$ even perfect matching $M$, $\exists$ perfect matching $M': M$ and $M'$ are disjoint and compatible
First observation: the even condition is necessary. Indeed, it is easy to find simple odd perfect matching $M$ such that doesn't exist a disjoint and compatible perfect matching $M'$. In the example below, for the first perfect matching with $3$ segments we see that none of four other perfect matchings is appropriate. (In fact for this example, there is only one possible pair $(M, M')$, the 2^{nd} and the 5^{th} matchings.)
The article [1] p. 9 explains how construct odd perfect matching with arbitrary size with no disjoint and compatible other matching. The idea is to consider the canonical perfect matching on points disposed on a circle like this:
This conjecture was proved in the article [3].
References ¶
 Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez, David Rappaport, Shakhar Smorodinsky, Diane L. Souvaine, Jorge Urrutia, David R. Wood. Compatible Geometric Matchings. arXiv.org, 2^{nd} version, January 16, 2008 Online PDF
 Greg Aloupis, Luis Barba, Stefan Langerman, Diane L. Souvaine. Bichromatic compatible matchings. arXiv.org, 3^{rd} version, November 26, 2013 Online PDF
 Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóoth. Disjoint Compatible Geometric Matchings. In Proceedings of SOCG, pp. 125134, New York, NY, USA, 2011. ACM
 PDF version of this Web page Online PDF
 Presentation slides in PDF Online PDF
 My other assignments for the INFOF420 Computational geometry course
 Projects from other students
 Graphic resource: Red warning 8 icon
 JavaScript. Mozilla Developer Network
 Plugins: MathJax, ViewerJS
 Wolfram MathWorld