文章基本信息

标题：Maximum Matchings in Geometric Intersection Graphs
本地全文：下载
作者：douard Bonnet ; Sergio Cabello ; Wolfgang Mulzer 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：31:1-31:17
DOI：10.4230/LIPIcs.STACS.2020.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：computational geometry; geometric intersection graph; maximum matching; disk graph; unit-disk graph