Planar Induced Subgraphs of Sparse Graphs
Glencora Borradaile, David Eppstein, and Pingan Zhu
Vol. 19, no. 1, pp. 281-297, 2015. Regular paper.
Abstract We show that every graph has an induced pseudoforest of at least nm/4.5 vertices, an induced partial 2-tree of at least nm/5 vertices, and an induced planar subgraph of at least nm/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 nm/6+o(m).
Submitted: November 2014.
Reviewed: March 2015.
Revised: April 2015.
Accepted: May 2015.
Final: May 2015.
Published: May 2015.
Communicated by Giuseppe Liotta
article (PDF)