Planar Induced Subgraphs of Sparse GraphsBorradaile, Glencora and Eppstein, David and Zhu, Pingan (2014) Planar Induced Subgraphs of Sparse Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 112(Official URL: http://dx.doi.org/10.1007/9783662458037_1). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_1
AbstractWe show that every graph has an induced pseudoforest of at least n − m/4.5 vertices, an induced partial 2tree 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 lineartime algorithms to find the respective induced subgraphs. We also show that the size of the largest K h minorfree graph in a given graph can sometimes be at most n − m/6 + o(m).
Actions (login required)
