Hardness of planar Hamiltonian decomposition and linear arboricity
I was getting ready to start writing a paper proving that Hamiltonian decomposition and linear arboricity are both \(\mathsf{NP}\)complete for planar graphs of maximum degree four. But then I realized that there’s a trivial proof, based on known results:

Finding a Hamiltonian cycle is \(\mathsf{NP}\)complete in 3regular planar graphs.^{1}

A 3regular graph has a Hamiltonian cycle if and only if its line graph has a Hamiltonian decomposition.^{2}^{3}

The line graph of a 3regular planar graph (its medial graph) is a 4regular planar graph.

A 4regular graph has a Hamiltonian decomposition if and only if the subgraph formed by removing an arbitrarily chosen single vertex has linear arboricity two.
That’s not enough for a paper, even though the linear arboricity result resolves a conjecture of Cygan, Hou, Kowalik, Lužar, and Wu (2012).^{4} So instead I’ll just leave this here, together with two illustrations I already drew of the gadgets for my proof. It’s a reduction from monotone planar 3sat, in which the variables are connected in a cycle in the plane, the 3sat clauses with all variables positive are on one side of the cycle, and the 3sat clauses with all variables negative are on the other side. Here “planar” means that if you represent each variable and clause as a vertex, draw edges from each variable to each clause that uses it, and also draw edges connecting consecutive variables in the cycle, the result is a planar graph.
My reduction adds a special “truthsetting gadget” to the cycle of variables. It represents the variables by regions of the plane, bounded by edges that are forced to belong to the same cycle in any Hamiltonian decomposition. The truthsetting gadget also forms regions of the plane, again bounded by edges that belong to the same cycle. The truthsetting regions extend through the clause gadgets so that they can reach the other clause gadgets on the other sides of them. A variable or negated variable is true if its region’s bounding edges are in the other cycle than the truthsetting gadget.
Here is the truthsetting gadget (the colored parts of the figure), and the (very simple) variable gadgets (gray shaded regions). Each variable gadget will have one loop of one color above the midline, and another loop of the opposite color below the midline.
And here is the clause gadget:
The 4 and 8vertex subunits in the light yellow disks force the partition into two parts of Hamiltonian cycles to be uniquely determined within each gadget, and the 5vertex subunits between the variable and clause gadget allow the variable to either connect to the parts of the cycles within the clause gadget or to remain separate from them. To construct a Hamiltonian decomposition, you have to have at least one true variable per clause, so that the clause gadget can be connected to the other cycle than the one from the truthsetting gadget. The reduction produces a multigraph rather than a graph, but that’s easy to fix by replacing some of the vertices by wheels.
Maybe the same idea of having a truthsetting gadget that passes through the clause gadgets can be useful in some other reductions?

Garey, M. R., Johnson, D. S., and Stockmeyer, L. (1974), “Some simplified \(\mathsf{NP}\)complete problems”, Proc. 6th ACM Symposium on Theory of Computing (STOC ‘74), pp. 47–63, doi:10.1145/800119.803884. ↩

Kotzig, Anton (1957), “Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades”, Časopis Pěst. Mat. 82: 76–92. As cited by Bondy and Häggkvist.^{5} ↩

Martin, Pierre (1976), “Cycles hamiltoniens dans les graphes 4réguliers 4connexes”, Aequationes Mathematicae 14 (1/2): 37–40, doi:10.1007/BF01836203. ↩

Cygan, Marek, Hou, JianFeng, Kowalik, Łukasz, Lužar, Borut, and Wu, JianLiang (2012), “A planar linear arboricity conjecture”, Journal of Graph Theory 69 (4): 403–425, doi:10.1002/jgt.20592. ↩

Bondy, J. A. and Häggkvist, R. (1981), “Edgedisjoint Hamilton cycles in 4regular planar graphs”, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157. ↩