  Proximity graphs have been studied for several decades, motivated by
applications in computational geometry, geography, data mining, and many other
fields. However, the computational complexity of classic graph problems on
proximity graphs mostly remained open. We now study 3-Colorability, Dominating
Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the
proximity graph classes relative neighborhood graphs, Gabriel graphs, and
relatively closest graphs. We prove that all of the problems remain NP-hard on
these graphs, except for 3-Colorability and Hamiltonian Cycle on relatively
closest graphs, where the former is trivial and the latter is left open.
Moreover, for every NP-hard case we additionally show that no
$2^{o(n^{1/4})}$-time algorithm exists unless the ETH fails, where n denotes
the number of vertices.
