Sebastian Feist:
Max-Cut on Planar Graphs
Kurzbeschreibung
Finding a maximum cut on general graphs is a well known NP-hard problem. However, if we are willing to limit ourselves to the class of planar graphs, it is possible to solve the problem in polynomial time. In this thesis we will have a closer look at such a polynomial time algorithm by Liers and Pardella, and use an implementation of it to see how a basic approximation algorithm for general maximum cut performs in the planar case.