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: https://drops.dagstuhl.de/opus/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