Parameterised Partially-Predrawn Crossing Number

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00129306" target="_blank" >RIV/00216224:14330/22:00129306 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46" target="_blank" >10.4230/LIPIcs.SoCG.2022.46</a>

Result language

angličtina

Original language name

Parameterised Partially-Predrawn Crossing Number

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

38th International Symposium on Computational Geometry (SoCG 2022)

ISBN

9783959772273

ISSN

1868-8969

e-ISSN

—

Number of pages

15

Pages from-to

„46:1“-„46:15“

Publisher name

Schloss Dagstuhl

Place of publication

Dagstuhl, Germany

Event location

Berlin, Germany

Event date

Jun 7, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—