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 language | English (US) |
---|---|
Pages (from-to) | 183-189 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 52 |
Issue number | 4 |
DOIs | |
State | Published - 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