# $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 > 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$$.
• Go ahead!$~~~~$ – domotorp Mar 22 at 6:01
• Thank you for sharing that idea! I think what you are saying is something like this: If possible, refine the largest face of size $> d$. For $d$ large enough, if you can do such a refinement, you will always decrease the sum of squares of face degrees. Continue doing this until you cannot decrease the sum of squares any further, at which point there cannot be any faces of degree $> d$. This is much easier than what I had in mind. :-) – Lorenzo Najt Apr 29 at 22:26