Planar embeddability of the vertices of a graph using a fixed point set is NP-hard - Cabello, Sergio (Journal of Graph Algorithms and Applications, 2006)
Let G=(V,E) be a graph with n vertices andlet P be a set of n points in the plane.We show that deciding whether there is aplanar straight-line embedding of G such that the vertices Vare embedded onto the points Pis NP-complete, even when G is 2-connected and 2-outerplanar.This settles an open problem posed in [,,]. <!---->