Planar Induced Subgraphs of Sparse Graphs

Abstract

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 $K_h$-minor-free graph in a given graph can sometimes be at most $n-m/6+o(m)$.

Accepted by Graph Drawing 2014. To appear in Journal of Graph Algorithms and Applications

Cited by in corpus (2)

• The Parameterized Complexity of Finding Point Sets with Hereditary Properties
• $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs