Separators for intersection graphs of spheres
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.22204
curl -X POST /api/v1/records/arxiv/2603.22204/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.22204/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'