Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.
Cabello, Sergio
Journal of Graph Algorithms and Applications, Tome 10 (2006), p. 353-363 / Harvested from The Electronic Library of Mathematics
Full (PDF)
Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:55397 
@article{05493568,
     title = {Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.},
     journal = {Journal of Graph Algorithms and Applications},
     volume = {10},
     year = {2006},
     pages = {353-363},
     zbl = {1161.68645},
     language = {en},
     url = {http://dml.mathdoc.fr/item/05493568}
}

Cabello, Sergio. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.. Journal of Graph Algorithms and Applications, Tome 10 (2006) pp. 353-363. http://gdmltest.u-ga.fr/item/05493568/