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(\rho^{3\omega/2}n^{\omega/2})\) time with high probability, where \(\rho\) is the density of the geometric objects and \(\omega>2\) is a constant such that \(n \times n\) matrices can be multiplied in \(O(n^\omega)\) 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^{\omega/2})\) time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in \([1, \Psi]\) can be found in \(O(\Psi^6\log^{11} n + \Psi^{12 \omega} n^{\omega/2})\) time with high probability.