MAXIMUM PLANAR SUBGRAPH

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A subset $E'\subseteq E$ such that $G'=\left(V,E'\right)$ is planar.
• MEASURE: Size of the subset, i.e., $\vert E'\vert$.

  
  

• Good News: Approximable within 2.5 [94].
• Bad News: APX-complete [94].
• Comment: Transformation from MINIMUM METRIC TRAVELING SALESPERSON PROBLEM with distances one and two. The complementary problem MINIMUM NONPLANAR EDGE DELETION is APX-hard. Variation in which the subgraph should be outerplanar is APX-complete and approximable within 1.5 [94].
• Garey and Johnson: GT27