Connected Matchings
<|reference_start|>Connected Matchings: We show that each set of $n\ge 2$ points in the plane in general position has a straight-line matching with at least $(5n+1)/27$ edges whose segments form a connected set, and such a matching can be computed in $O(n \log n)$ time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has $\lceil \frac{n-1}{3}\rceil$ edges. We also consider a colored version, where each edge of the matching should connect points with different colors.<|reference_end|>
@article{aichholzer2024connected,
    title={Connected Matchings},
    author={Oswin Aichholzer, Sergio Cabello, Viola M'esz'aros, Patrick
  Schnider, Jan Soukup},
    journal={arXiv preprint arXiv:2407.06131},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.06131},
    primaryClass={cs.CG math.CO}
}