Abstract
Let π be a set of straightline segments in the plane, potentially crossing, and let c be a positive integer. We denote by P the union of the endpoints of the straightline segments of π and of the intersection points between pairs of segments. We say that π has a nearestneighbor decomposition into c parts if we can partition P into c point sets Pβ, β¦ , P_c such that π is the union of the nearest neighbor graphs on Pβ, β¦ , P_c. We show that it is NPcomplete to decide whether π can be drawn as the union of c β₯ 3 nearestneighbor graphs, even when no two segments cross. We show that for c = 2, it is NPcomplete in the general setting and polynomialtime 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 nearestneighbor 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 kpartite graphs, we give additional, more efficient constructions. We furthermore show that there are subdivisions of nonplanar graphs that are not conflict graphs. Lastly, we show a separator lemma for conflict graphs.
BibTeX  Entry
@InProceedings{cleve_et_al:LIPIcs.SWAT.2022.21,
author = {Cleve, Jonas and Grelier, Nicolas and Knorr, Kristin and L\"{o}ffler, Maarten and Mulzer, Wolfgang and Perz, Daniel},
title = {{NearestNeighbor Decompositions of Drawings}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {21:121:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16181},
URN = {urn:nbn:de:0030drops161812},
doi = {10.4230/LIPIcs.SWAT.2022.21},
annote = {Keywords: nearestneighbors, decompositions, drawing}
}
Keywords: 

nearestneighbors, decompositions, drawing 
Collection: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) 
Issue Date: 

2022 
Date of publication: 

22.06.2022 