I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are straight-line segments connecting the corresponding vertices), check whether the graph admits a non-crossing Hamiltonian path (i.e. there exists a path in the graph that covers all the vertices but does not intersect itself). Are there any hardness results (or efficient algorithms) known for this problem?
References, if any, on the above problem will be appreciated. The only reference that I am currently aware of is this, but I don't think it addresses the above problem directly.
