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, Würzburg, Germany , 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
ID Code:1416

Repository Staff Only: item control page


Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. J. Graph Theory 113, 113–123 (2001) MR 1859785

Borradaile, G., Eppstein, D., Zhu, P.: Planar induced subgraphs of sparse graphs (2014), arXiv:1408.5939

Borradaile, G., Klein, P., Marx, D., Mathieu, C.: Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports 3(10), 36–57 (2014)

Călinescu, G., Fernandes, C.G., Finkler, U., Karloff, H.: A better approximation algorithm for finding planar subgraphs. J. Algorithms 27(2), 269–302 (1998) MR 1622397

Cheng, C., McDermid, E., Suzuki, I.: Planarization and acyclic colorings of subcubic claw-free graphs. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 107–118. Springer, Heidelberg (2011) MR 2914703

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs, 1st edn. Prentice-Hall (1998)

Edwards, K., Farr, G.: An algorithm for finding large induced planar subgraphs. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 75–80. Springer, Heidelberg (2002) MR 2410446

Edwards, K., Farr, G.: Planarization and fragmentability of some classes of graphs. Discrete Math. 308(12), 2396–2406 (2008) MR 2410446

Edwards, K., Farr, G.: Improved upper bounds for planarization and series-parallelization of degree-bounded graphs. Electron. J. Combin. 19(2), 25 (2012) MR 2928640

Halldórsson, M.M., Lau, H.C.: Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. J. Graph Algorithms Appl. 1(3), 1–13 (1997) MR 1600712

Kawarabayashi, K.-I.: Planarity allowing few error vertices in linear time. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 639–648 (2009) MR 2648441

Kawarabayashi, K.-i., Reed, B.: Computing crossing number in linear time. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 382–390 (2007) MR 2402463

Kostochka, A.V.: The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz 38, 37–58 (1982) MR 0713722

Kostochka, A.V.: Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4(4), 307–316 (1984) MR 0779891

Lubotzky, A., Philips, R., Sarnak, R.: Ramanujan graphs. Combinatorica 8, 261–277 (1988) MR 0963118

Morgan, K., Farr, G.: Approximation algorithms for the maximum induced planar and outerplanar subgraph problems. J. Graph Algorithms Appl. 11(1), 165–193 (2007) MR 2354168

Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95(2), 261–265 (1984) MR 0735367

Thomason, A.: The extremal function for complete minors. J. Combinatorial Theory, Series B 81(2), 318–338 (2001) MR 1814910