On planar graphs, many classic algorithmic problems enjoy a certain square root phenomenon and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time
$2^{O(\sqrt{n})}$ on an $n$-vertex planar graph, while no $2^{o(n)}$ algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH). The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to $2^{o(\sqrt{n})}$. In some cases, a
similar speedup can be obtained for 2-dimensional geometric problems, for example, there are $2^{O(\sqrt{n}\log n)}$ time algorithms for Independent Set on unit disk graphs or for TSP on 2-dimensional point sets.

In this paper, we explore whether such a speedup is possible for geometric coloring problems. On the one hand, geometric objects can behave similarly to planar graphs: \textsc{3-Coloring} can be solved in time $2^{O(\sqrt{n})}$ on the intersection graph of $n$ unit disks in the plane and, assuming the ETH, there is no such algorithm with running time $2^{o(\sqrt{n})}$. On the other hand, if the number $\ell$ of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of $n$ unit disks with $\ell$ colors cannot be solved in time $2^{o(n)}$, assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number $\ell$ of colors increases: If we restrict the number of colors to $\ell=\Theta(n^{\alpha})$ for some $0\le \alpha\le 1$, then the problem of coloring the intersection graph of $n$ unit disks with $\ell$ colors

- can be solved in time $\exp \left( O(n^{\frac{1+\alpha}{2}}\log n) \right)=\exp \left( O(\sqrt{n\ell}\log n) \right)$, and

- cannot be solved in time $\exp \left ( o(n^{\frac{1+\alpha}{2}})\right )=\exp \left( o(\sqrt{n\ell}) \right)$, unless the ETH fails.

joint work with
Csaba Biró, Édouard Bonnet, Dániel Marx, and Paweł Rzazewski

PS: I am happy to give a talk, but if there are too many talks already, I am also happy not to give a talk.