Nearest-Neighbor Decompositions of Drawings

09/05/2022
āˆ™
by   Jonas Cleve, et al.
āˆ™
0
āˆ™

Let š’Ÿ 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 š’Ÿ and of the intersection points between pairs of segments. We say that š’Ÿ has a nearest-neighbor decomposition into c parts if we can partition P into c point sets P_1, ā€¦, P_c such that š’Ÿ is the union of the nearest neighbor graphs on P_1, ā€¦, P_c. We show that it is NP-complete to decide whether š’Ÿ can be drawn as the union of cā‰„ 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 š’Ÿ 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 š’Ÿ. The vertices of the conflict graph are the connected components of š’Ÿ, 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 āˆŖ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset