Exact Crossing Number Parameterized by Vertex Cover

D 2019

Exact Crossing Number Parameterized by Vertex Cover

HLINĚNÝ, Petr a Abhisekh SANKARAN

Základní údaje

Originální název

Exact Crossing Number Parameterized by Vertex Cover

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Abhisekh SANKARAN (356 Indie)

Vydání

Cham, GD 2019: Graph Drawing and Network Visualization, od s. 307-319, 13 s. 2019

Nakladatel

Springer, Lecture Notes in Computer Science, volume 11904

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL open access preprint

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00108274

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-35801-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-35802-0_24

UT WoS

000612918800024

Klíčová slova anglicky

Graph drawing; Crossing number; Parameterized complexity; Vertex cover

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 14. 4. 2021 21:46, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when parameterized by the vertex cover size. This is a notable advance since we know only very few nontrivial examples of graph classes with unbounded and yet efficiently computable crossing number. Our result can be viewed as a strengthening of a previous result of Lokshtanov [arXiv, 2015] that Optimal Linear Arrangement is in FPT when parameterized by the vertex cover size, and we use a similar approach of reducing the problem to a tractable instance of Integer Quadratic Programming as in Lokshtanov’s paper.

Návaznosti

GA17-00837S, projekt VaV

Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems

Citovat

HLINĚNÝ, Petr a Abhisekh SANKARAN. Exact Crossing Number Parameterized by Vertex Cover. In GD 2019: Graph Drawing and Network Visualization. Cham: Springer, Lecture Notes in Computer Science, volume 11904, 2019, s. 307-319. ISBN 978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0_24.

@inproceedings{1646079,
   author = {Hliněný, Petr and Sankaran, Abhisekh},
   address = {Cham},
   booktitle = {GD 2019: Graph Drawing and Network Visualization},
   doi = {http://dx.doi.org/10.1007/978-3-030-35802-0_24},
   keywords = {Graph drawing; Crossing number; Parameterized complexity; Vertex cover},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-35801-3},
   pages = {307-319},
   publisher = {Springer, Lecture Notes in Computer Science, volume 11904},
   title = {Exact Crossing Number Parameterized by Vertex Cover},
   url = {http://dx.doi.org/10.1007/978-3-030-35802-0_24},
   year = {2019}
}

TY  - JOUR
ID  - 1646079
AU  - Hliněný, Petr - Sankaran, Abhisekh
PY  - 2019
TI  - Exact Crossing Number Parameterized by Vertex Cover
PB  - Springer, Lecture Notes in Computer Science, volume 11904
CY  - Cham
SN  - 9783030358013
KW  - Graph drawing
KW  - Crossing number
KW  - Parameterized complexity
KW  - Vertex cover
UR  - http://dx.doi.org/10.1007/978-3-030-35802-0_24
N2  - We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when parameterized by the vertex cover size. This is a notable advance since we know only very few nontrivial examples of graph classes with unbounded and yet efficiently computable crossing number. Our result can be viewed as a strengthening of a previous result of Lokshtanov [arXiv, 2015] that Optimal Linear Arrangement is in FPT when parameterized by the vertex cover size, and we use a similar approach of reducing the problem to a tractable instance of Integer Quadratic Programming as in Lokshtanov’s paper.
ER  -

HLINĚNÝ, Petr a Abhisekh SANKARAN. Exact Crossing Number Parameterized by Vertex Cover. In \textit{GD 2019: Graph Drawing and Network Visualization}. Cham: Springer, Lecture Notes in Computer Science, volume 11904, 2019, s.~307-319. ISBN~978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}24.

Podrobný výpis o publikaci