Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs

We study the recognition complexity of subgraphs of k -connected planar cubic graphs where k ∈ \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)factor -problem for the fixed embedding case, and SPQR-trees for the variable embedding case. Secondly, we prove -hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.