On the maximum number of edges in plane graph with fixed exterior face degree

Abstract

A well known Euler's formula consequence's corollary in graph theory states that: For a connected simple planar graph with $n$ vertices and $m$ edges, and girth $g$, we have $m\le \frac{g}{g-2}(n-2)$. We show that a connected simple plane graph with $n$ vertices and girth $g$, and exterior face of degree $h$ has at most $\frac{g}{g-2}(n-2)-\frac{1}{g-2}(h-g)$ edges. A \emph{convex hull $g$-angulation} is a connected plane graph in which the exterior face is a simple $h$-cycle and all inner faces are $g$-cycles. For a given set $S$ of $n$ point in the plane having $h$ points in the boundary of its convex hull, we present the necessary and sufficient condition to obtain a convex hull $g$-angulation on $S$. We also determine the number of edges and inner faces in the convex hull $g$-angulation.

5 pages