MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 – 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.

For the class of non-planar bipartite graphs, the only results I've seen are for sparse bipartite graphs. See section 2 in the recent article "Short proofs of some extremal results" by Conlon, Fox, and Sudakov.

share|cite|improve this answer

Well, a planar graph usually has only one outer face. But if you want your planar graph to have only one face then you require your graph to be a tree (if tere is any cycle in your graph, then you get to have a face somewhere...)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.