Pancyclicity and NP-completeness in planar graphs

DOI10.1016/S0166-218X(99)00163-8zbMath0939.05027DBLPjournals/dam/LiCM00OpenAlexW2008914847WikidataQ56235005 ScholiaQ56235005MaRDI QIDQ1962068

Eric Mendelsohn, Derek Gordon Corneil, Ming-Chu Li

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

complexityplanar graphsNP-completenessvertex pancyclicity

Mathematics Subject Classification ID

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

Related Items (10)

Global cycle properties of locally isometric graphs ⋮ Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs ⋮ Pancyclicity in switching classes ⋮ Unnamed Item ⋮ On Saito's conjecture and the Oberly-Sumner conjectures ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Unnamed Item ⋮ The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Global cycle properties in graphs with large minimum clustering coefficient

Cites Work

• Pairs of edge-disjoint Hamiltonian circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unnamed Item

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