Abstract
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, 3Coloring, Hamiltonian Cycle, Dominating Set can be solved in time 2^O(sqrt{n}) on an nvertex 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 2dimensional 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 2dimensional 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: 3Coloring 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 L of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of n unit disks with L colors cannot be solved in time 2^o(n), assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number L of colors increases: If we restrict the number of colors to L=Theta(n^alpha) for some 0<=alpha<=1, then the problem of coloring the intersection graph of n unit disks with L colors
* can be solved in time exp(O(n^{{1+alpha}/2}log n))=exp( O(sqrt{nL}log n)), and
* cannot be solved in time exp(o(n^{{1+alpha}/2}))=exp(o(sqrt{nL})), unless the ETH fails.
More generally, we consider the problem of coloring ddimensional unit balls in the Euclidean space and obtain analogous results showing that the problem
* can be solved in time exp(O(n^{{d1+alpha}/d}log n))=exp(O(n^{11/d}L^{1/d}log n)), and
* cannot be solved in time exp(n^{{d1+alpha}/depsilon})= exp (O(n^{11/depsilon}L^{1/d})) for any epsilon>0, unless the ETH fails.
BibTeX  Entry
@InProceedings{bir_et_al:LIPIcs:2017:7180,
author = {Csaba Bir{\'o} and {\'E}douard Bonnet and D{\'a}niel Marx and Tillmann Miltzow and Pawel Rzazewski},
title = {{FineGrained Complexity of Coloring Unit Disks and Balls}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {18:118:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7180},
URN = {urn:nbn:de:0030drops71800},
doi = {10.4230/LIPIcs.SoCG.2017.18},
annote = {Keywords: unit disk graphs, unit ball graphs, coloring, exact algorithm}
}
Keywords: 

unit disk graphs, unit ball graphs, coloring, exact algorithm 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 