Abstract
We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set $\mathcal{D}$ of $n$ unit disks inducing a unit-disk graph $G_{\mathcal{D}}$ and a number $p\in[n]$, one can partition $\mathcal{D}$ into $p$ subsets $\mathcal{D}_{1},\dots,\mathcal{D}_{p}$ such that for every $i\in[p]$ and every $\mathcal{D}^{\prime}\subseteq\mathcal{D}_{i}$, the graph obtained from $G_{\mathcal{D}}$ by contracting all edges between the vertices in $\mathcal{D}_{i}\backslash\mathcal{D}^{\prime}$ admits a tree decomposition in which each bag consists of $O(p+|\mathcal{D}^{\prime}|)$ 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(\sqrt{k}\log k)}\cdot 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})}\cdot n^{O(1)}$ time. We also show that the problem cannot be solved in $2^{o(\sqrt{k})}\cdot n^{O(1)}$ time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.