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.