Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses of planar cubic bipartite graphs. An interesting subclass contains infinite number of graphs and excludes infinite number of graphs.
More importantly, Which hard problems do remain hard on nontrivial subclasses of planar cubic bipartite graphs?
Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs, but this is not actually a restriction: every cubic planar bipartite graph is 2-connected. It is a well-known open problem whether 3-connected cubic planar bipartite graphs always have Hamiltonian cycles, but if they do not then the problem is NP-complete for them as well.
(One of my recent papers looked at some related connectivity classes of cubic planar bipartite graphs but not from the point of view of NP-hardness.)
Does subclass mean a class of subgraphs? If yes:
In holographic algorithms, $(2,3)$-regular bipartite graphs are studied, i.e., the nodes on the lefthand side have degree 2 and on the righthand side have degree 3. The dichotomy theorems by Kowalczyk and Cai (STACS 2010) yield hard problems for such graphs.
Cubic Montone Planar 1-in-3 SAT: 1-in-3 SAT without negated variables and where each variable is in exactly 3 clauses, and the incidence graph (the bipartite graph where the variables and the clauses are the vertex sets) is planar.
http://arxiv.org/abs/math/0003039
If you are willing to relax the 3-regularity, this may be relevant: Planar-3-Connected (3,4)-SAT, 3SAT but where each variable is in at most 4 clauses, and the incidence graph is polyhedral (3-connected and planar).
Nick Wormald: Models of random regular graphs in Surveys in COmbinatorics, London Math Society Lecture Notes Series, 276 Cambridge University Press, 1999, 239-298, 1999
