  It is a well-known fact that hamiltonicity in planar cubic graphs is an
NP-complete problem. This implies that the existence of an A-trail in plane
eulerian graphs is also an NP-complete problem even if restricted to planar
3-connected eulerian graphs. In this paper we deal with hamiltonicity in planar
cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces
in G/Q and study the algorithmic complexity of finding such (quasi) spanning
trees of faces. We show, in particular, that if Barnette's Conjecture is false,
then hamiltonicity in 3-connected planar cubic bipartite graphs is an
NP-complete problem.
