Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems - Morgan, Kerri; Farr, Graham (Journal of Graph Algorithms and Applications, 2007)
The task of finding the largest subset of verticesof a graph that induces a planar subgraph is known as the MaximumInduced Planar Subgraph problem (MIPS). In this paper, some newapproximation algorithms for MIPS are introduced. The results ofan extensive study of the performance of these and existing MIPSapproximation algorithms on randomly generated graphs arepresented. Efficient algorithms for finding large inducedouterplanar graphs are also given. One of these algorithms isshown to find an induced outerplanar subgraph with at least3n/(d+5/3) vertices for graphs of n vertices with maximumdegree at most d. The results presented in this paper indicatethat most existing algorithms perform substantially better thanthe existing lower bounds indicate. <!---->