Greedy Spanners in Euclidean Spaces Admit Sublinear Separators: arxiv.org/abs/2107.06490

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 · · ·

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