1
$\begingroup$

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we consider it in special cases of graphs.

$\endgroup$
  • $\begingroup$ Does, e.g., this answer your question? $\endgroup$ – dkaeae Aug 6 at 15:29
  • $\begingroup$ Thanks for your comment. Yes it shows finding Hamiltonian path in planar graph is NP-Complete. Next question would be what if the points are inside a polygon, two points are connected to each other which the connecting line between them is completely inside the polygon? $\endgroup$ – inaderi Aug 7 at 6:05
1
$\begingroup$

Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other.

[1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I'm thinking about the case in which points are inside a polygon and are connected if they are visible to each other. In this case I cant use this result. It seems this isn't easy $\endgroup$ – inaderi Aug 7 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.