Key points are not available for this paper at this time.
Abstract 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.
Goetze et al. (Tue,) studied this question.