# Hard problems on subclasses of planar cubic bipartite graphs

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.)

• Thanks David. Could you please point me to a reference that surveys different characterizations of planar cubic bipartite graphs and how to generate them. I'm aware of a characterization of planar bipartite graphs in terms of contact graphs of vertical and horizontal line segments. – Mohammad Al-Turkistany Apr 12 '11 at 6:29
• Don't know of such a reference, sorry. – David Eppstein Apr 12 '11 at 21:22

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.

• No, subclass is not a class of subgraphs. Here it means a restricted class of planar cubic bipartite graphs. – Mohammad Al-Turkistany Apr 11 '11 at 19:34

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).

http://dx.doi.org/10.1016/0166-218X(94)90143-0

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

• Hi Josep, I'm not sure if this answers the question. Random cubic graphs aren't necessarily planar nor are they bipartite. I couldn't find a good online version of this article and MathSciNet does not mention anything about conditioning on either of the abovementioned properties... Could you please clarify? – RJK Apr 14 '11 at 22:15