Balanced Line Separators of Unit Disk Graphs

Paz Carmi, Man Kwun Chiu, Matthew J. Katz +6

We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $\ell$ such that $\…