Maximum Matchings in Geometric Intersection Graphs

Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer

Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O(\ddot{I}{}^{3\ddot{I}‰/2}{n}^{\ddot{I}‰/2})$ time with high probability, w…