Outerplanar Turán numbers of cycles and paths

Abstract

A graph is outerplanar if it can be embedded in a plane such that all vertices lie on its outer face. The outerplanar Turán number of a given graph $H$, denoted by ${\mathrm{ex}}_{\mathcal{O}\mathcal{P}}(n,H)$, is the maximum number of edges over all outerplanar graphs on $n$ vertices which do not contain a copy of $H$. In this paper, the outerplanar Turán numbers of cycles and paths are completely determined.

18 pages, 6 figures