Exact Crossing Number Parameterized by Vertex Cover

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

HLINĚNÝ Petr SANKARAN Abhisekh

Rok publikování 2019
Druh Článek ve sborníku
Konference GD 2019: Graph Drawing and Network Visualization
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www
Doi http://dx.doi.org/10.1007/978-3-030-35802-0_24
Klíčová slova Graph drawing; Crossing number; Parameterized complexity; Vertex cover
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.