Crossing Number is Hard for Kernelization
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.
SoCG