$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree? Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$.

Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, what is the smallest (known) $\mathscr{C}_d$ ?



My thoughts:

I know $\mathscr{C}_3$ consists only of graphs isomorphic to $K_4$, by an Euler's formula argument. So necessarily $d &gt; 4$.

$\mathscr{C}_4$ is already infinite, and the number of isomorphism types of size $\leq k$ grow exponentially fast: once you have a triangle, you can subdivide two of its edges and connect them with an edge. You can also subdivide four sided faces by connecting opposite edges with a new edge. You can then subdivide a triangle into an m level pyramid, and subdivide the levels with vertical lines, which gives $2^m$ choices based on the next subdivision point being 'right' or 'left' of the previous one. So $\mathscr{C}_4$ is (to me) a plausible candidate.



I know the following two closely related theorems:

1) Hamiltonian cycle is NP-complete on the class of cubic, 3-connected simple plane graphs ( $\mathscr{C}_{\infty}$ in my notation): http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf

In addition, they show that they can force the girth to be at least 5. This is opposite from the spirit of my question.

2) Hamiltonian cycle is NP-complete on the class of 3-connected plane graphs with face degree $3$ (i.e. maximal plane graphs): http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf
In the first paper which you link to (Garey-Johnson-Tarjan) they show how to construct a 3-input OR on Figure 6. This gadget has the property that it can link 3 edges with the only requirement that at least one of them needs to be used. So start from your original cubic 3-connected graph and suppose that it has a face larger than $d$. Then insert this gadget into this face onto edges $e,f,g$, where $e$ and $f$ are adjacent, and $g$ is opposite to them. Since $e$ and $f$ are adjacent, anyhow one of them had to be used in the original cubic graph, so the gadget will do nothing. On the other hand, since $g$ is on the opposite side of the face, the size $d$ will be almost halved. Here 'almost' means that this inserted gadget also has some size $c$, so the new faces will have size at most $d/2+c$. Repeating this gets rid of all faces whose size is more than $2c$.