A Note on the Practicality of Maximal Planar Subgraph Algorithms

Markus Chimani, Karsten Klein, Tilo Wiedera

Given a graph $G$, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of $G$ with the maximum number of edges. There are several heuristic, approximative,…