Small feedback vertex sets in planar digraphs

Abstract

Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \frac{5n-5}{9}$ if $g=4$, $|X|\le \frac{2n-5}{4}$ if $g=5$, and $|X|\le \frac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.

5 pages, 1 figure - v3 final version