Geodesic
Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 165-193.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00141
Keywords: Graph algorithms, Maximum Induced Planar Subgraph, Planarity, Outerplanarity, Approximation algorithms, Vertex deletion problems 
@article{JGAA_2007_11_1_a6,
     author = {Kerri Morgan and Graham Farr},
     title = {Approximation {Algorithms} for the {Maximum} {Induced} {Planar} and {Outerplanar} {Subgraph} {Problems}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {165--193},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00141},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00141/}
}
TY  - JOUR
AU  - Kerri Morgan
AU  - Graham Farr
TI  - Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 165
EP  - 193
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00141/
DO  - 10.7155/jgaa.00141
LA  - en
ID  - JGAA_2007_11_1_a6
ER  - 
%0 Journal Article
%A Kerri Morgan
%A Graham Farr
%T Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
%J Journal of Graph Algorithms and Applications
%D 2007
%P 165-193
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00141/
%R 10.7155/jgaa.00141
%G en
%F JGAA_2007_11_1_a6
Kerri Morgan; Graham Farr. Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 165-193. doi : 10.7155/jgaa.00141. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00141/

Cité par Sources :