Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs

Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt

We study the recognition complexity of subgraphs of k-connected planar cubic graphs for k = 1, 2, 3. We present polynomial-time algorithms to recognize subgraphs of 1- and 2-connec…