# “Face cover” of a planar graph

What is the size of the smallest set of vertices in planar graph when removed the remaining graph has only one face (outer face)?

Is this parameter well studied? Does it have a name? A case of special interest is the class of bipartite 2-connected graphs.

-
Dear hbm, since you have posted a few questions recently, some of which have been one-liners, without much motivation or background, I would like to point you to the page mathoverflow.net/howtoask – Gjergji Zaimi May 29 '12 at 8:29
I just did not what to search for. Thanks for the info. – hbm May 29 '12 at 9:35

The minimum number of vertices one can remove in order to make the graph acyclic (which is the only meaning I can give to "one outer face") is called the decycling number of a graph. There is a famous conjecture here by Albertson and Berman, and independently Akiyama and Watanabe which says that the decycling number of a planar graph on $n$ vertices is at most $n/2$. This appears to be a very difficult problem. It is known to be true for triangle free planar graphs.
In fact for triangle free planar graphs (and therefore bipartite planar graphs) the decycling number is $\le \frac{15n-24}{32}$. This is proved in "Large Induced Forests in Triangle-free Planar Graphs" by M.R. Salavatipour. It was recently improved to $\frac{57n-72}{128}$ by L. Kowalik, B. Lužar, R. Škrekovski in "An improved bound on the largest induced forests for triangle-free planar graphs". The proofs make use of the Discharging method, which you might have seen in the context of the 4 color theorem.