HLINĚNÝ, Petr and 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, p. 307-319. ISBN 978-3-030-35801-3. Available from: https://dx.doi.org/10.1007/978-3-030-35802-0_24.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Exact Crossing Number Parameterized by Vertex Cover
Authors HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Abhisekh SANKARAN (356 India).
Edition Cham, GD 2019: Graph Drawing and Network Visualization, p. 307-319, 13 pp. 2019.
Publisher Springer, Lecture Notes in Computer Science, volume 11904
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Switzerland
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
WWW URL open access preprint
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/19:00108274
Organization unit Faculty of Informatics
ISBN 978-3-030-35801-3
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-030-35802-0_24
UT WoS 000612918800024
Keywords in English Graph drawing; Crossing number; Parameterized complexity; Vertex cover
Tags core_A, firank_A, formela-conference
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Changed: 14/4/2021 21:46.
Abstract
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.
Links
GA17-00837S, research and development projectName: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Investor: Czech Science Foundation
PrintDisplayed: 19/9/2024 14:59