Deciding whether a planar graph has a cubic subgraph is NP-complete

DOI10.1016/0012-365X(94)90277-1zbMath0795.68150MaRDI QIDQ1318823

Iain A. Stewart

Publication date: 4 April 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completeplanar graphcubic subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (13)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ On locating cubic subgraphs in bounded-degree connected bipartite graphs ⋮ Editing to a Planar Graph of Given Degrees ⋮ Finding regular subgraphs in both arbitrary and planar graphs ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Complete problems for monotone NP ⋮ Graph editing problems with extended regularity constraints ⋮ Editing to a planar graph of given degrees ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Parameterized Graph Editing with Chosen Vertex Degrees

Cites Work

• Planar Formulae and Their Uses
• The complexity of satisfiability problems
• Unnamed Item

This page was built for publication: Deciding whether a planar graph has a cubic subgraph is NP-complete