Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments

Markus Chimani, Ivo Hedtke, Tilo Wiedera

Given a graph $G$, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of $G$ with the maximum number of edges. The only known non-trivial exact algorithm utiliz…