Planar Induced Subgraphs of Sparse Graphs

Borradaile, Glencora and Eppstein, David and Zhu, Pingan (2014) Planar Induced Subgraphs of Sparse Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 1-12(Official URL:

Full text not available from this repository.


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).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_1
Classifications: G Algorithms and Complexity > G.840 Planarization
M Methods > M.300 Dynamic / Incremental / Online
Z Theory > Z.999 Others

Actions (login required)

View Item View Item