2015/12/08 by Petr Hliněný, Hliněný, Petr, Marek Derňár +1
Computer Science · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1512.02379
openalex publication_date 2015/12/08 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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]. 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.