A linear edge kernel for two-layer crossing minimization

The two-layer crossing minimization problem (TLCM), given a bipartite graph G with n vertices and a positive integer k, asks whether G has a two-layer drawing with at most k   crossings. We consider a simple generalization of TLCM called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k)O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(klog⁡k)+nO(1)2O(klog⁡k)+nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n2O(k3)n.