Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00141
Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
Vol. 11, no. 1, pp. 165-193, 2007. Regular paper.
Abstract The task of finding the largest subset of vertices
of a graph that induces a planar subgraph is known as the Maximum
Induced Planar Subgraph problem (MIPS). In this paper, some new
approximation algorithms for MIPS are introduced. The results of
an extensive study of the performance of these and existing MIPS
approximation algorithms on randomly generated graphs are
presented. Efficient algorithms for finding large induced
outerplanar graphs are also given. One of these algorithms is
shown to find an induced outerplanar subgraph with at least
3n/(d+5/3) vertices for graphs of n vertices with maximum
degree at most d. The results presented in this paper indicate
that most existing algorithms perform substantially better than
the existing lower bounds indicate.
|
Journal Supporters
|