A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization

We give a subexponential fixed parameter algorithm for one‐sided crossing minimization. It runs in $O(k{2}^{\sqrt{2k}}+n)$ time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of $O(\sqrt{k})$ in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in $2^{O(\sqrt{k}\log k)}+n^{O(1)}$ time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.