Greedy Spanners in Euclidean Spaces Admit Sublinear Separators:

My SoCG'21 result with Hadi Khodabandeh that 2d greedy spanners have separators of size \(O(\sqrt{n})\) used crossing-based methods heavily dependent on planarity. This new preprint by Hung Le and Cuong Than uses different ideas to find separators of size \(O(n^{1-1/d})\), optimal in any dimension \(d\). Their work also extends from Euclidean spaces to doubling spaces.

· · Web · 0 · 0 · 1
Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!