Maximum Matchings in Geometric Intersection Graphs

Abstract

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, where $\ddot{I}$ is the density of the geometric objects and $\ddot{I}‰>2$ is a constant such that $n\times n$ matrices can be multiplied in $O(n^{\ddot{I}}‰)$ time. The same result holds for any subgraph of $G$, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in $O(n^{\ddot{I}‰/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1,\hat{I}¨]$ can be found in $O(\hat{I}{¨}^6{\log }^{11}n+\hat{I}{¨}^{12\ddot{I}‰}{n}^{\ddot{I}‰/2})$ time with high probability.

25 pages, 1 figure; a preliminary version appeared at STACS 2020