Abstract
In the Proofs of NP-completeness seminar at the Chair i1 Complexity and Algorithms of RWTH Aachen University, I was assigned the proof of NP-completeness of the Graph Genus Problem. This summary of the proof given by C. Thomassen elaborates on the mathematical structures and foundations used and the insights gained in the proof.