$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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Does, e.g., this answer your question? $\endgroup$– dkaeaeAug 6, 2019 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$– inaderiAug 7, 2019 at 6:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\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$– inaderiAug 7, 2019 at 6:15