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({\rho }^{3\omega /2}{n}^{\omega /2})$ time with high probability, wher…