Noncrossing Hamiltonian paths in geometric graphs

Abstract

Hamiltonian path is a path visiting all vertices of a graph. The path is non-crossing if it does not cross itself.

We study what is the minimum number edges of complete geometic graph you have to remove to guarantee there is no non-crossing Hamiltonian path.

Keywords

• Noncrossing
• Hamiltonian
• paths
• geometric
• graphs