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.ICALP.2021.72
URN: urn:nbn:de:0030-drops-141412
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14141/
Go to the corresponding LIPIcs Volume Portal

Ganian, Robert ; Hamm, Thekla ; Klute, Fabian ; Parada, Irene ; Vogtenhuber, Birgit

Crossing-Optimal Extension of Simple Drawings

pdf-format:
LIPIcs-ICALP-2021-72.pdf (1 MB)

Abstract

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge.
In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.

BibTeX - Entry

@InProceedings{ganian_et_al:LIPIcs.ICALP.2021.72,
  author =	{Ganian, Robert and Hamm, Thekla and Klute, Fabian and Parada, Irene and Vogtenhuber, Birgit},
  title =	{{Crossing-Optimal Extension of Simple Drawings}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{72:1--72:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14141},
  URN =		{urn:nbn:de:0030-drops-141412},
  doi =		{10.4230/LIPIcs.ICALP.2021.72},
  annote =	{Keywords: Simple drawings, Extension problems, Crossing minimization, FPT-algorithms}
}

Keywords: Simple drawings, Extension problems, Crossing minimization, FPT-algorithms
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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