| Title: | Maximum matchings in geometric intersection graphs |
|---|
| Authors: | ID Bonnet, Édouard (Author)
ID Cabello, Sergio (Author)
ID Mulzer, Wolfgang (Author) |
|---|
| Files: |  PDF - Presentation file, download (576,69 KB)
MD5: CFA5DBABF17761B11ACC25F11DBAF784
 URL - Source URL, visit https://link.springer.com/article/10.1007/s00454-023-00564-3
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| 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(\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. |
|---|
| Keywords: | computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.10.2023 |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | str. 550-579 |
|---|
| Numbering: | Vol. 70, iss. 3 |
|---|
| PID: | 20.500.12556/DiRROS-18632  |
|---|
| UDC: | 004.42:515.17 |
|---|
| ISSN on article: | 0179-5376 |
|---|
| DOI: | 10.1007/s00454-023-00564-3 |
|---|
| COBISS.SI-ID: | 163998979 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 08.04.2024 |
|---|
| Views: | 1016 |
|---|
| Downloads: | 497 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
