Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives

Pascal Kunz, Till Fluschnik, Rolf Niedermeier +1

Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computation…