PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
May 29, 20260 citationsOpen Access

Separators for Intersection Graphs of Spheres

View Full Paper
JFJacob FoxJTJonathan Tidor

Key Points

  • The research aims to demonstrate the existence of optimal separators for intersection graphs of balls and spheres in any dimension.
  • Proved existence of balanced separators for intersection graphs of spheres in ℝ^d.
  • Analyzed parameters n (number of spheres) and m (number of edges).
  • Established bounds for separator sizes based on dimensions and parameters.
  • The intersection graph of n spheres in ℝ^d has a balanced separator of size O_d(m^{1/d}n^{1-2/d}).
  • The established bound is best possible concerning the involved parameters.

Abstract

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 ℝᵈ has m edges, then it contains a balanced separator of size Od (m^1/dn^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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Fox et al. (2026) studied this question.

synapsesocial.com/papers/6a192f88fab5b468c4418a2dhttps://doi.org/10.4230/lipics.socg.2026.50
Ask AI
Helpful
Bookmark
Share
View Full Paper