  The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph $H$ of
a given graph $G$ such that $H$ has maximum edge cardinality. For more than two
decades, the only known non-trivial exact algorithm was based on integer linear
programming and Kuratowski's famous planarity criterion. We build upon this
approach and present new constraint classes, together with a lifting of the
polyhedron, to obtain provably stronger LP-relaxations, and in turn faster
algorithms in practice. The new constraints take Euler's polyhedron formula as
a starting point and combine it with considering cycles in $G$. This paper
discusses both the theoretical as well as the practical sides of this
strengthening.
