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

Chuzo Iwamoto, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

Let A={C1, C2,..., Cn} be an arrangement of Jordan curves in the plane lying in general position, i.e., every properly intersects at least one other curve, no two curves touch each other and no three meet at a common intersection point. The Jordan-curve arrangement graph of A has as its vertices the intersection points of the curves in A, and two vertices are connected by an edge if their corresponding intersection points are adjacent on some curve in A. We further assume A is such that the resulting graph has no multiple edges. Under these conditions it is shown that determining whether Jordan-curve arrangement graphs are Hamiltonian is NP-complete.

Original languageEnglish (US)
Pages (from-to)183-189
Number of pages7
JournalInformation Processing Letters
Volume52
Issue number4
DOIs
StatePublished - Nov 25 1994

Keywords

  • Arrangements of Jordan curves
  • Computational complexity
  • Computational geometry
  • Hamiltonian circuit
  • NP-completeness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Finding Hamiltonian circuits in arrangements of Jordan curves is NP-complete'. Together they form a unique fingerprint.

Cite this