Nearest-Neighbor Decompositions of Drawings

Abstract

Let $\mathcal{D}$ be a set of straight-line segments in the plane, potentially crossing, and let $c$ be a positive integer. We denote by $P$ the union of the endpoints of the straight-line segments of $\mathcal{D}$ and of the intersection points between pairs of segments. We say that $\mathcal{D}$ has a nearest-neighbor decomposition into $c$ parts if we can partition $P$ into $c$ point sets $P_1,\dots ,P_c$ such that $\mathcal{D}$ is the union of the nearest neighbor graphs on $P_1,\dots ,P_c$. We show that it is NP-complete to decide whether $\mathcal{D}$ can be drawn as the union of $c\ge 3$ nearest-neighbor graphs, even when no two segments cross. We show that for $c=2$, it is NP-complete in the general setting and polynomial-time solvable when no two segments cross. We show the existence of an $O(\log n)$-approximation algorithm running in subexponential time for partitioning $\mathcal{D}$ into a minimum number of nearest-neighbor graphs. As a main tool in our analysis, we establish the notion of the conflict graph for a drawing $\mathcal{D}$. The vertices of the conflict graph are the connected components of $\mathcal{D}$, with the assumption that each connected component is the nearest neighbor graph of its vertices, and there is an edge between two components $U$ and $V$ if and only if the nearest neighbor graph of $U\cup V$ contains an edge between a vertex in $U$ and a vertex in $V$. We show that string graphs are conflict graphs of certain planar drawings. For planar graphs and complete $k$-partite graphs, we give additional, more efficient constructions. We furthermore show that there are subdivisions of non-planar graphs that are not conflict graphs. Lastly, we show a separator lemma for conflict graphs.

17 pages, 18 figures; a preliminary version appeared at SWAT 2022