Maximum matchings in geometric intersection graphs

Bonnet, Édouard (avtor), Cabello, Sergio (avtor), Mulzer, Wolfgang (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.10.2023
• Leto izida: 2023
• Št. strani: Str. 550-579
• Številčenje: Vol. 70, iss. 3
• PID: 20.500.12556/RUL-155610
• UDK: 004.42:515.17
• ISSN pri članku: 0179-5376
• DOI: 10.1007/s00454-023-00564-3
• COBISS.SI-ID: 163998979
• Datum objave v RUL: 08.04.2024

Gradivo je del revije

• Naslov: Discrete & computational geometry
• Skrajšan naslov: Discrete comput. geom.
• Založnik: Springer
• ISSN: 0179-5376
• COBISS.SI-ID: 25342208

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.