Publications with Pingan Zhu
- Planar induced subgraphs of sparse graphs.
G. Borradaile, D. Eppstein, and P. Zhu.
arXiv:1408.5939.
22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 1–12.
J. Graph Algorithms & Applications 19 (1): 281–297, 2015.We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that m/5.22 vertices are sufficient and m/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.