Barnette's conjecture is the statement that every 3-connected cubic
planar bipartite graph is Hamiltonian. Goodey showed that the conjecture
holds when all faces of the graph have either 4 or 6 sides. We
generalize Goodey's result by showing that when the faces of such a
graph are 3-colored, with adjacent faces having different colors, if two of the
three color classes contain only faces with either 4 or 6 sides, then the
conjecture holds. More generally, we consider 3-connected cubic planar
graphs that are not necessarily bipartite, and show that if the faces
of such a graph are 2-colored, with every vertex incident to one blue
face and two red faces, and all red faces have either 4 or 6 sides,
while the blue faces are arbitrary, provided that blue faces with either
3 or 5 sides are adjacent to a red face with 4 sides (but without any
assumption on blue faces with $4,6,7,8,9,\ldots$ sides), then the graph
is Hamiltonian. The approach is to consider the reduced graph obtained
by contracting each blue face to a single vertex, so that the reduced
graph has faces corresponding to the original red faces and with either 2 or 3
sides, and to show that such a reduced graph always contains a
proper quasi spanning tree of faces. In general, for a reduced graph
with arbitrary faces, we give a polynomial time algorithm based on
spanning tree parity to decide if the reduced graph has a spanning tree
of faces having 2 or 3 sides, while to decide if the reduced graph has
a spanning tree of faces with 4 sides or of arbitrary faces is NP-complete
for reduced graphs of even degree.
As a corollary, we show that whether a reduced graph has a noncrossing
Euler tour has a polynomial time algorithm if all vertices have degree
4 or 6, but is NP-complete if all vertices have degree 8.
Finally, we show that if Barnette's conjecture is false, then the
question of whether a graph in the class of the conjecture is Hamiltonian
is NP-complete.