Minimizing the Number of Arcs Linking a Permutation of Points in the Plane
Stéphane Durocher, Chris Gray, James A. King · 2006
Given a finite set of points P in R 2 and a permutation of P, f : P ! P, what is the minimum number of arcs required to connect the points of P such that every point p P is adjacent to f(p) along an arc and no two arcs cross? We show this question is NP-complete.