MAXIMUM PLANAR SUBGRAPH

Next: MINIMUM EDGE DELETION K-PARTITION Up: Subgraphs and Supergraphs Previous: MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH Index

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

Viggo Kann
2000-03-20