A different approach to Jit's problem: remove my Q

We consider the following problem that is mentioned by Jit a couple of times: Given an $n$-vertex plane graph $G$, find the smallest subset $C$ of edges such that the intersection of the endpoints of $C$ with the boundary vertices of every face of $G$ is non-empty. Informally, we say that $C$ covers all the faces of $G$. It is known that $n/3$ is a lower bound on the size of $C$.

By using four color theorem, Everett and Rivera-Campo (1997) showed that $G$ can be covered with a set of $2n/5$ edges. By a different coloring approach, Jit et al. (2003) showed that $G$ can be covered by $n/3+q$ edges where $q$ is the number of quadrilateral faces. We go back to four color theorem and show how to cover G with $n/3+q/9$ edges. Moreover, if the quadrilaterals are far from each other we show how to cover G with $n/3$ edges.

In the worst case $q$ is about $n$, and thus, the $2n/5$ bound is still better than $n/3+q/9$. We show how to get a $2n/5$ covering with a non-coloring approach. This is a promising approach to improve the upper bound.