A Better Approximation Algorithm for Finding Planar Subgraphs |
| |
Authors: | Gruia C?linescu Cristina G Fernandes Ulrich Finkler Howard Karloff |
| |
Institution: | aCollege of Computing, Georgia Institute of Technology, Atlanta, Georgia, 30332-0280;bMax-Planck-Institut für Informatik, D-66123, Saarbrücken, Germany |
| |
Abstract: | The MAXIMUM PLANAR SUBGRAPH problem—given a graphG, find a largest planar subgraph ofG—has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time approximation algorithm for this NP-Complete problem was known to achieve a performance ratio larger than 1/3, which is achieved simply by producing a spanning tree ofG. We present the first approximation algorithm for MAXIMUM PLANAR SUBGRAPH with higher performance ratio (4/9 instead of 1/3). We also apply our algorithm to find large outerplanar subgraphs. Last, we show that both MAXIMUM PLANAR SUBGRAPH and its complement, the problem of removing as few edges as possible to leave a planar subgraph, are Max SNP-Hard. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|