  Given an edge-weighted graph $G$ on $n$ nodes, the NP-hard Max-Cut problem
asks for a node bipartition such that the sum of edge weights joining the
different partitions is maximized. We propose a fixed-parameter tractable
algorithm parameterized by the number $k$ of crossings in a given drawing of
$G$. Our algorithm achieves a running time of $O(2^k \cdot p(n + k))$, where
$p$ is the polynomial running time for planar Max-Cut. The only previously
known similar algorithm [8] is restricted to 1-planar graphs (i.e., at most one
crossing per edge) and its dependency on $k$ is of order $3^k$ . A direct
consequence of our result is that Max-Cut is fixed-parameter tractable w.r.t.
the crossing number, even without a given drawing. Moreover, the results
naturally carry over to the minor crossing number.
