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.SoCG.2022.46
URN: urn:nbn:de:0030-drops-160547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16054/
Go to the corresponding LIPIcs Volume Portal

Hamm, Thekla ; Hliněný, Petr

Parameterised Partially-Predrawn Crossing Number

pdf-format:
LIPIcs-SoCG-2022-46.pdf (1 MB)

Abstract

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension problems.

BibTeX - Entry

@InProceedings{hamm_et_al:LIPIcs.SoCG.2022.46,
  author =	{Hamm, Thekla and Hlin\v{e}n\'{y}, Petr},
  title =	{{Parameterised Partially-Predrawn Crossing Number}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16054},
  URN =		{urn:nbn:de:0030-drops-160547},
  doi =		{10.4230/LIPIcs.SoCG.2022.46},
  annote =	{Keywords: Crossing Number, Drawing Extension, Partial Planarity, Parameterised Complexity}
}

Keywords: Crossing Number, Drawing Extension, Partial Planarity, Parameterised Complexity
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

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