2026-07-22T18:45:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5934 2024-03-06T10:37:19Z ddc:004 open_access

Crossing Number is Hard for Kernelization Hlinený, Petr Dernár, Marek crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed-parameter tractable for the parameter k [Grohe, STOC 2001]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Hlinený and Marek Dernár 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.42 urn:nbn:de:0030-drops-59347 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.42 eng https://creativecommons.org/licenses/by/3.0/legalcode