Parameterised Partially-Predrawn Crossing Number

D 2022

Parameterised Partially-Predrawn Crossing Number

HAMM, Thekla a Petr HLINĚNÝ

Základní údaje

Originální název

Parameterised Partially-Predrawn Crossing Number

Autoři

HAMM, Thekla (276 Německo) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

LIPIcs Vol. 224. Dagstuhl, Germany, 38th International Symposium on Computational Geometry (SoCG 2022), od s. "46:1"-"46:15", 15 s. 2022

Nakladatel

Schloss Dagstuhl

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

DOI open access

Kód RIV

RIV/00216224:14330/22:00129306

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-227-3

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46

Klíčová slova anglicky

Crossing Number; Drawing Extension; Parameterised Complexity; Partial Planarity

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 6. 1. 2023 11:16, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Návaznosti

GA20-04567S, projekt VaV

Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

Citovat

HAMM, Thekla a Petr HLINĚNÝ. Parameterised Partially-Predrawn Crossing Number. Online. In Goaoc, Xavier and Kerber, Michael. 38th International Symposium on Computational Geometry (SoCG 2022). LIPIcs Vol. 224. Dagstuhl, Germany: Schloss Dagstuhl, 2022, s. "46:1"-"46:15", 15 s. ISBN 978-3-95977-227-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46.

@inproceedings{2243997,
   author = {Hamm, Thekla and Hliněný, Petr},
   address = {Dagstuhl, Germany},
   booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46},
   edition = {LIPIcs Vol. 224},
   editor = {Goaoc, Xavier and Kerber, Michael},
   keywords = {Crossing Number; Drawing Extension; Parameterised Complexity; Partial Planarity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-227-3},
   pages = {"46:1"-"46:15"},
   publisher = {Schloss Dagstuhl},
   title = {Parameterised Partially-Predrawn Crossing Number},
   url = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46},
   year = {2022}
}

TY  - JOUR
ID  - 2243997
AU  - Hamm, Thekla - Hliněný, Petr
PY  - 2022
TI  - Parameterised Partially-Predrawn Crossing Number
PB  - Schloss Dagstuhl
CY  - Dagstuhl, Germany
SN  - 9783959772273
KW  - Crossing Number
KW  - Drawing Extension
KW  - Parameterised Complexity
KW  - Partial Planarity
UR  - http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46
N2  - 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.
ER  -

HAMM, Thekla a Petr HLINĚNÝ. Parameterised Partially-Predrawn Crossing Number. Online. In Goaoc, Xavier and Kerber, Michael. \textit{38th International Symposium on Computational Geometry (SoCG 2022)}. LIPIcs Vol. 224. Dagstuhl, Germany: Schloss Dagstuhl, 2022, s.~''46:1''-''46:15'', 15 s. ISBN~978-3-95977-227-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2022.46.

Podrobný výpis o publikaci