A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929268506755072 |
|---|---|
| author | Aronov, Boris de Berg, Mark Theocharous, Leonidas |
| author_facet | Aronov, Boris de Berg, Mark Theocharous, Leonidas |
| contents | Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $\mathbb{R}^2$ and let $\mathcal{D}=\{D_1,\ldots,D_n\}$ be a set of geodesic disks with respect to the metric $d$. We prove that $\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in $\mathcal{D}$, has a clique-based separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators.
Our clique-based separator yields an algorithm for $q$-COLORING that runs in time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks $D_i$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04905 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$ Aronov, Boris de Berg, Mark Theocharous, Leonidas Computational Geometry F.2.2 Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $\mathbb{R}^2$ and let $\mathcal{D}=\{D_1,\ldots,D_n\}$ be a set of geodesic disks with respect to the metric $d$. We prove that $\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in $\mathcal{D}$, has a clique-based separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for $q$-COLORING that runs in time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks $D_i$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes. |
| title | A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$ |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2403.04905 |