Bonnet, Édouard ;
Cabello, Sergio ;
Mulzer, Wolfgang
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(ρ^{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.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2020:11892,
author = {{\'E}douard Bonnet and Sergio Cabello and Wolfgang Mulzer},
title = {{Maximum Matchings in Geometric Intersection Graphs}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {31:131:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11892},
URN = {urn:nbn:de:0030drops118926},
doi = {10.4230/LIPIcs.STACS.2020.31},
annote = {Keywords: computational geometry, geometric intersection graph, maximum matching, disk graph, unitdisk graph}
}
04.03.2020
Keywords: 

computational geometry, geometric intersection graph, maximum matching, disk graph, unitdisk graph 
Seminar: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Issue date: 

2020 
Date of publication: 

04.03.2020 