What does maximal planar graph mean?
A graph G is maximal planar graph means that G is planar, but if we add one more edge between a pair of non-adjacent vertices, the resulting graph is not planar.
(1) If G is a planar graph of order n>=3 and size m is maximal planar , then m=3n-6
Proof. Denote by r the number of regions of G. In G the boundary of ...
It is proven that a planar graph of order n>=3 and size m is maximal planar if and only if m=3n-6.