Next: MINIMUM EDGE DELETION K-PARTITION
Up: Subgraphs and Supergraphs
Previous: MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
  Index
- 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
Viggo Kann
1999-04-22