Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my perspective, it doesn't seem too impressive, the argument is rather elementary, but I can't find another paper which states what I found. The closest I could find was Jan Florek's On Barnette's Conjecture, which is about a subcase which I was previously aware of.

Definitions: It is well-known that a cubic polyhedral graph, $P$, is Hamiltonian iff its dual, $D$, can be partitioned into two sets of vertices, $A,B$, such that the induced subgraphs $D[A]$ and $D[B]$ are both trees. A dual with this condition is said to have a tree-partitioning.

Since a dual, $D$, of cubic bipartite polyhedral graph is triangularized, and has a unique 3-coloring, I found it easier to think about removing all vertices in one color class, which gives us a 2-connected bipartite graph, $S$, with a fixed planar embedding. To recover $D$ from $S$, for each face, $f$ in $S$, we add a vertex $v_f$, and add edges between $v_f$ and all vertices $u$ incident to $f$. This recovery process is well defined, and shall be denoted as $D(S)$.

My result says: if a bipartite 2-connected planar embedded graph, $S$, is constructible (in a way defined below), then $D(S)$ has a tree partitioning, and thus is the dual of a Hamiltonian bipartite cubic polyhedral graph.

Construction Method:

Throughout, the "exterior cycle" of a connected component is the cycle that creates a polygon with the largest area with respect to how the component is embedded.

1. We start with $S_1$ being an even cycle graph $C_{2k_0}$, with a planar embedding. Currently, all vertices of $S_1$ make up its "exterior cycle".
2. If the exterior cycle has four vertices, we may choose to stop at $S_i$, or may continue
3. Embed a new even cycle graph $C_{2k_i}$ as a new component, such that all vertices are outside the exterior cycle of $S_i$
4. Choose two paths of length $2 \leq l \leq 4 $ along the exterior cycles of your two components, $p_1 = v_1,v_2 \dots v_l, p_2 = u_1,u_2,\dots u_l$.
5. Add edges $(v_j,u_j)$ for all $1 \leq j \leq l$, and contract said edges. (moving the location of $u_j$ to $v_j$ in the embedding)
6. Return to step 2.

Any $S_i$ at which we can stop at step 2, is constructible. My result above is gotten from a rather simple inductive argument. The class of graphs which are made Hamiltonian contains those proven by Florek, in fact, this is specifically the case when $k_i = 2$ for $i > 0$, and one may use a even shorter argument for this case.

Is this result known, and if not, does the fact that the family of graphs is rather difficult to describe detract from its value?

Edit: I just realized that there is an second result of my methods. If $P$ is a cubic bipartite polyhedral graph, and also constructible, then $P$ is Hamiltonian.

While I am aware that there are non 2-connected bipartite planar graphs, such as the tetrahedron with all edges subdivided, I cannot immediately come up with any non-constructible graphs that are also cubic and polyhedral. Presumably, there are such graphs, but if not, then Barnette's conjecture is solved!

So, if one could provide any examples of non-constructible cubic polyhedral bipartite graphs, that would be of interest.