Pancyclicity and NP-completeness in planar graphs

DOI10.1016/S0166-218X(99)00163-8MaRDI QIDQ1962068zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Eric Mendelsohn, Mingchu Li, Derek G. Corneil

Publication date 29 June 2000

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

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00163-8

zbMATH Keywords

complexityNP-completenessplanar graphsvertex pancyclicity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

A graph is called {\(v\)-pancyclic} if it contains a cycle of length \(l\) containing a given vertex \(v\) for \(3\leq l\leq n\), and a graph \(G\) is called vertex pancyclic if \(G\) is \(v\)-pancyclic for all \(v\). The authors show that it is NP-complete to determine whether a 3-connected cubic planar graph is \(v\)-pancyclic for given vertex \(v\), it is NP-complete to determine whether a 3-connected cubic planar graph is pancyclic, and it is NP-complete to determine whether a 3-connected planar graph is vertex pancyclic. They also show that every maximal outplanar graph is vertex pancyclic.

Recommendations

• Vertex pancyclic graphs
• scientific article; zbMATH DE number 1744073
• scientific article; zbMATH DE number 867697
• Vertex pancyclic graphs
• scientific article; zbMATH DE number 3857154

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Pairs of edge-disjoint Hamiltonian circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(11)

• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Exact algorithms for finding longest cycles in claw-free graphs
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• On Saito's conjecture and the Oberly-Sumner conjectures
• Global cycle properties of locally isometric graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Pancyclicity in switching classes
• scientific article; zbMATH DE number 1504827 (Why is no real title available?)
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• Global cycle properties in graphs with large minimum clustering coefficient
• Vertex-pancyclism in edge-colored complete graphs with restrictions in color transitions

This page was built for publication: Pancyclicity and NP-completeness in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962068)