Geodesic
Planar Induced Subgraphs of Sparse Graphs
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 281-297.

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

We show that every graph has an induced pseudoforest of at least n−m/4.5 vertices, an induced partial 2-tree of at least n−m/5 vertices, and an induced planar subgraph of at least n−m/5.2174 vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest Kh-minor-free graph in a given graph can sometimes be at most n−m/6+o(m).
DOI : 10.7155/jgaa.00358
Keywords: induced subgraphs, planar, partial k-trees 
@article{JGAA_2015_19_1_a12,
     author = {Glencora Borradaile and David Eppstein and Pingan Zhu},
     title = {Planar {Induced} {Subgraphs} of {Sparse} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {281--297},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00358},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00358/}
}
TY  - JOUR
AU  - Glencora Borradaile
AU  - David Eppstein
AU  - Pingan Zhu
TI  - Planar Induced Subgraphs of Sparse Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 281
EP  - 297
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00358/
DO  - 10.7155/jgaa.00358
LA  - en
ID  - JGAA_2015_19_1_a12
ER  - 
%0 Journal Article
%A Glencora Borradaile
%A David Eppstein
%A Pingan Zhu
%T Planar Induced Subgraphs of Sparse Graphs
%J Journal of Graph Algorithms and Applications
%D 2015
%P 281-297
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00358/
%R 10.7155/jgaa.00358
%G en
%F JGAA_2015_19_1_a12
Glencora Borradaile; David Eppstein; Pingan Zhu. Planar Induced Subgraphs of Sparse Graphs. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 281-297. doi : 10.7155/jgaa.00358. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00358/

Cité par Sources :