A New Approximation Algorithm for Finding Heavy Planar Subgraphs

摘要

We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3, which is obtained by any algorithm that produces a maximum weight spanning tree in G. Based on the Berman-Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3 + 1/72 and at most 5/12. We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8. Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2) for the NP-hard MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.