Scholarlink

<p>We study the recognition complexity of subgraphs of <i>k</i>-connected planar cubic graphs where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({k \in \{0, 1, 2, 3\}}\)</EquationSource> </InlineEquation>. 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 <span>Generalized (Anti)factor</span>-problem for the fixed embedding case, and SPQR-trees for the variable embedding case. Secondly, we prove <Emphasis FontCategory="SansSerif">NP</Emphasis>-hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月25日

查看全文
  • Miriam Goetze,
  • Paul Jungeblut,
  • Torsten Ueckerdt

摘要

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 NP-hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.