Recognition Complexity of Subgraphs of 2- and 3-Connected Planar Cubic Graphs

Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt

Abstract

This paper investigates the computational complexity of determining whether a planar graph $G$ is a subgraph of a $k$-connected, 3-regular (cubic) planar graph $H$. This problem, known as the 3-augmentation problem, is central to understanding graph structure and has significant implications for the long-standing 3-edge-colorability problem. We show that while the problem is solvable in polynomial time for $k=1$ and $k=2$, it becomes NP-complete for $k=3$.

Introduction

A fundamental question in algorithmic graph theory is the "growth" potential of graphs: can a given simple planar graph $G$ be augmented into a more structured supergraph $H$? Specifically, this research focuses on subgraphs of $k$-connected, 3-regular planar graphs. The motivation is twofold: advancing the theory of graph augmentation and exploring the boundaries of the 3-edge-colorability problem for planar graphs.

Example of a graph $G_2$ being a subgraph of a 2-connected cubic planar graph $H_2$.

The 3-Augmentation Problem

The core challenge is the 3-augmentation problem. Given a planar subcubic graph $G$ (maximum degree 3), the goal is to determine if edges and vertices can be added to form a supergraph $H$ that is planar, 3-regular, and $k$-connected. This problem is intrinsically linked to the 3-edge-colorability problem. According to the Four-Color Theorem and Tait's work, every 2-connected, 3-regular planar graph is 3-edge-colorable. Identifying subgraphs of such graphs provides a pathway toward solving the polynomial-time decidability of 3-edge-colorability for general planar subcubic graphs.

Methodology

The researchers categorized their approach based on the flexibility of the graph's embedding:

  1. Fixed Embedding: For a fixed planar embedding, the problem is reduced to the Generalized Factor problem. By constructing a bipartite graph mapping vertices to faces, the authors use "B-factors" to determine if valid edges can be added within faces to meet connectivity goals.
  2. Variable Embedding: When the embedding is not fixed, the search space grows exponentially. The authors employ SPQR-trees to decompose 2-connected graphs into triconnected components, applying dynamic programming to evaluate if any valid embedding supports a 2-connected 3-augmentation.
  3. NP-Hardness: To prove NP-completeness for the 3-connected case ($k=3$), a reduction from Planar-Monotone-3SAT was developed. This involved designing intricate gadgets (variable, splitter, and clause gadgets) that map boolean satisfiability to graph augmentation possibilities.

Results and Complexity Landscape

The study provides a comprehensive map of the complexity landscape for 3-augmentation. A significant "complexity jump" occurs at $k=3$. While 1- and 2-connectivity requirements allow for efficient polynomial-time algorithms, 3-connectivity introduces coordination constraints that render the problem NP-complete.

Complexity landscape of the 3-augmentation problem across different connectivity requirements and embedding types.

Key findings include:

  • $k=1$ (Connected): Solvable in $O(n^2)$ (fixed) or $O(n)$ (variable) time.
  • $k=2$ (2-Connected): Solvable in $O(n^4)$ (fixed) or $O(n^2)$ (variable) time.
  • $k=3$ (3-Connected): NP-complete for variable embeddings, even if the input graph is already connected.

Conclusion

This work refines previous results by showing that the 3-connected case remains hard even when an arbitrary number of new vertices can be added. A remaining open problem is the complexity of the 3-connected case with a fixed embedding. Furthermore, while 2-connected 3-augmentation is sufficient for 3-edge-colorability, it is not necessary, leaving a gap for future research to bridge.

Summary updated

Abstract

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-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 NP-hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.
BibTeX
@article{goetze2026recognition,
  author = {Miriam Goetze and Paul Jungeblut and Torsten Ueckerdt},
  title = {{Recognition Complexity of Subgraphs of 2- and 3-Connected Planar Cubic Graphs}},
  journal = {Algorithmica},
  year = {2026},
  doi = {10.1007/s00453-025-01350-8},
}
Figure