Set of vertices intersecting all faces of a planar graph Does anyone know if the following problem exists in the literature: Given a planar graph, find a minimum set of vertices intersecting all of its faces.
 A: Such a set is called a face hitting set of the planar graph. (Note that in general, this depends not only on the graph itself, but also on the embedding you choose.) This terminology does not come out of nowhere: a "hitting set" for any other kind of object is a set that intersects every instance of that object.
In particular, a cycle hitting set is also called a feedback vertex set, which intersects every cycle of a graph. If the graph is planar, then any feedback vertex set is of course a face hitting set, since all faces are cycles. I am given to understand that the paper Connected feedback vertex set in planar graphs by A. Grigoriev and R. Sitters proves a half-converse: the size of the smallest feedback vertex set is at most twice the size of the smallest face hitting set. (But I can't check, since I don't have access to the paper from home.)
For some reason, lots of people are interested in finding connected face hitting sets. See for instance Connecting face hitting sets in planar graphs by Pascal Schweitzer and Patrick Schweitzer. This paper is where I got my citation for the at-most-twice-the-size fact above. It also proves a different interesting result: in a connected planar graph with minimum degree $3$, any face hitting set of size $n$ is contained in a connected face hitting set of size $5n-6$. (A factor of $5$ is the price you pay for connectivity.)
Why minimum degree $3$, by the way? Because if degree-$2$ vertices are allowed, you could subdivide each edge a billion times, inflating the size of a connected face hitting set tremendously while not affecting the general problem at all. But that's maybe more detail than you wanted to know.
