Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete

DOI10.1016/0020-0190(94)90125-2zbMath0823.68084OpenAlexW2034646155MaRDI QIDQ1341680

Chuzo Iwamoto, Godfried T. Toussaint

Publication date: 9 January 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90125-2

zbMATH Keywords

Hamiltonian circuitJordan-curve

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

Hamiltonicity and colorings of arrangement graphs ⋮ PROPERTIES OF ARRANGEMENT GRAPHS ⋮ Regular non-Hamiltonian polyhedral graphs

Cites Work

• Computing simple circuits from a set of line segments
• A linear algorithm for embedding planar graphs using PQ-trees
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• A Theorem on Planar Graphs
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On Envelopes of Arrangements of Lines
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete