Minimal pentagulations of $n$-gons

Abstract

A planar graph $G$ is called a pentagulation of an $n$-gon ($n\ge$ is an integer) if all faces of $G$ are pentagons, except one, which is an $n$-gon. A $3$-connected pentagulation $G$ of an $n$-gon is called minimal if it has the smallest number of pentagons among all such $3$-connected pentagulations. It is known that minimal pentagulations of the $3$-gon and $4$-gon contain 15 and 14 pentagons, respectively. We determined all minimal pentagulations of $n$-gons for all $n$ such that $3\le n\le 12$ using computer calculations. The calculations employed the plantri package, which generates all planar triangulations for a given number of vertices. We also present several open questions on this topic.

arXiv comment34 pages, 21 figures, any comments are welcome