Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs

Christine Dahn, Nils M. Kriege, Petra Mutzel +1

We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number $k$ of the given embedding. A…