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

Abstract We study the recognition complexity of subgraphs of k -connected planar cubic graphs where $${k \in \{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.