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?
Hard problems on subclasses of planar cubic bipartite graphs
cc.complexity theory;reference request;graph classes
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.)