Separators in sphere intersection graphs

Prelegent(ci)

Rose McCarty

Język referatu

angielski

Termin

17 stycznia 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

We discuss the sphere dimension of graphs. This is the smallest integer d such that the graph can be represented as the intersection graph of a collection of spheres in R^d. We show that graphs with small sphere dimension have small balanced separators, as long as they exclude some complete bipartite graph K_{t,t}. This property can be used to develop divide-and-conquer algorithms.

This is joint work with James Davies, Agelos Georgakopoulos, and Meike Hatzel.

---