Recognition Complexity of Subgraphs of ${\textbf {k}}$-Connected Planar Cubic Graphs

We study the recognition complexity of subgraphs of k-connected planar cubic graphs where k E {0, 1, 2, 3}. We present polynomial-time algorithms to recognize subgraphs of 1-and 2-connected planar cubic graphs, both in the variable and fixed embedding setting. The main tools involve the GENERALIZED (ANTI)FACTORproblem for the fixed embedding case, and SPQR-trees for the variable embedding case. Secondly, we prove NP-hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.