Planar graph

Question

I have a Planar graph with n nodes and e edges that slices the plain into s section.

What is the upper limit for s as a function of n and e and e/n?

I'm trying to find how little memory I can count on some code using.

---

It's easy to show that e is not more than n*(n-1)/2 but I have a feeling that it's going to be a small integer. For a n ~= 10 case I have with fixed node position, that overestimates the limit by a factor of 2.

Answer 1

you should look here http://en.wikipedia.org/wiki/Euler_characteristic might help

Answer 2

It can be proven by induction that e <= 3*n - 6. So e/n < 3 and so s/n < 2.