2026-07-22T15:45:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11892 2024-03-06T10:48:57Z ddc:004 open_access

Maximum Matchings in Geometric Intersection Graphs Bonnet, Édouard Cabello, Sergio Mulzer, Wolfgang computational geometry geometric intersection graph maximum matching disk graph unit-disk graph 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(ρ^{3ω/2}n^{ω/2}) time with high probability, where ρ is the density of the geometric objects and ω>2 is a constant such that n × n matrices can be multiplied in O(n^ω) 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^{ω/2}) time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in [1, Ψ] can be found in O(Ψ⁶log^11 n + Ψ^{12 ω} n^{ω/2}) time with high probability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Sergio Cabello and Wolfgang Mulzer 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.31 urn:nbn:de:0030-drops-118926 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode