True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs

We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set \ (D\) of \ (n\) unit disks inducing a unit-disk graph \ (G₃\) and a number \ (p\), one can partition \ (D\) into \ (p\) subsets \ (D₁, , D₏\) such that for every \ (i\) and every \ (D^₈\), the graph obtained from \ (G₃\) by contracting all edges between the vertices in \ (D₈^\) admits a tree decomposition in which each bag consists of \ (O (p+|D^|) \) cliques. Our theorem can be viewed as an analog for unit-disk graphs of the structural theorems for planar graphs and almost-embeddable graphs proved recently by Marx et al. SODA ’22 and Bandyapadhyay et al. SODA ’22. By applying our structural theorem, we give several new combinatorial and algorithmic results for unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem for unit-disk graphs, resolving an open question in the work by Panolan et al. SODA ’19. On the algorithmic side, we obtain a new algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in \ (2^O (k k) n^O (1) \) time, where \ (k\) denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. SODA ’22 which runs in \ (2^O (k^{27/28) } n^O (1) \) time. We also show that the problem cannot be solved in \ (2^o (k) n^O (1) \) time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.