Separators in sphere intersection graphs

Speaker(s)

Rose McCarty

Language of the talk

English

Date

Jan. 17, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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.

---