0

Let G be a planar graph. I'm looking for results on counting the number of missing edge in order to triangulate G. There is the trivial one SUM((k-3)Ck) for k >= 4 and Ck being the number of cycles of length k. Others?

Thanks for any pointer. Gianfranco

flag
3 
 This question confuses me. Don't planar triangulations on $n$ vertices have $3n-6$ edges? So we can just take $3n-6-|E(G)|$. – Tony Huynh Apr 15 2010 at 22:28
(Assuming that "triangulation" here requires the outer face to be triangular as well.) Unrelatedly, the phrase "crossing number of planar graph" in the title seems rather ill-advised to me. – JBL Apr 15 2010 at 23:50

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.