Separators for intersection graphs of spheres
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908907159420928 |
|---|---|
| author | Fox, Jacob Tidor, Jonathan |
| author_facet | Fox, Jacob Tidor, Jonathan |
| contents | We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension $d$. One of our results is that if an intersection graph of $n$ spheres in $\mathbb{R}^d$ has $m$ edges, then it contains a balanced separator of size $O_d(m^{1/d}n^{1-2/d})$. This bound is best possible in terms of the parameters involved. The same result holds if the balls and spheres are replaced by fat convex bodies and their boundaries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22204 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Separators for intersection graphs of spheres Fox, Jacob Tidor, Jonathan Computational Geometry Combinatorics We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension $d$. One of our results is that if an intersection graph of $n$ spheres in $\mathbb{R}^d$ has $m$ edges, then it contains a balanced separator of size $O_d(m^{1/d}n^{1-2/d})$. This bound is best possible in terms of the parameters involved. The same result holds if the balls and spheres are replaced by fat convex bodies and their boundaries. |
| title | Separators for intersection graphs of spheres |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2603.22204 |