License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.21
URN: urn:nbn:de:0030-drops-161812
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16181/
Go to the corresponding LIPIcs Volume Portal

Cleve, Jonas ; Grelier, Nicolas ; Knorr, Kristin ; Löffler, Maarten ; Mulzer, Wolfgang ; Perz, Daniel

Nearest-Neighbor Decompositions of Drawings

pdf-format:
LIPIcs-SWAT-2022-21.pdf (1 MB)

Abstract

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₁, … , P_c such that ? is the union of the nearest neighbor graphs on P₁, … , 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.

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 =	{{Nearest-Neighbor Decompositions of Drawings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16181},
  URN =		{urn:nbn:de:0030-drops-161812},
  doi =		{10.4230/LIPIcs.SWAT.2022.21},
  annote =	{Keywords: nearest-neighbors, decompositions, drawing}
}

Keywords: nearest-neighbors, decompositions, drawing
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI