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

### MAXIMUM PLANAR SUBGRAPH

- INSTANCE: Graph .
- SOLUTION: A subset such that is planar.
- MEASURE: Size of the subset, i.e., |E'|.

- Good News: Approximable within 2.5 [86].
- Bad News: APX-complete [86].
- 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 [86].

- Garey and Johnson: GT27