$k$-angulations

Prosenjit Bose

Carleton University

A straight-line embedding of a planar graph is called a $k$-angulation if every face except the outerface is a simple polygon on $k$ vertices and the outerface is a cycle. It is a strong $k$-angulation if in addition, the outerface is the convex hull. We will present various results on the characterization of planar point sets (in general position) that admit $k$-angulations for various values of $k$. For example, every planar point set admits a $k$-angulation when $k=3$.