# David Eppstein - Publications

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

Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.