License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.31
URN: urn:nbn:de:0030-drops-118926
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11892/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Cabello, Sergio ; Mulzer, Wolfgang

Maximum Matchings in Geometric Intersection Graphs

pdf-format:
LIPIcs-STACS-2020-31.pdf (0.6 MB)

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:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11892},
  URN =		{urn:nbn:de:0030-drops-118926},
  doi =		{10.4230/LIPIcs.STACS.2020.31},
  annote =	{Keywords: computational geometry, geometric intersection graph, maximum matching, disk graph, unit-disk graph}
}

Keywords: computational geometry, geometric intersection graph, maximum matching, disk graph, unit-disk graph
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI