Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00132
Planar embeddability of the vertices of a graph using a fixed point set is NPhard
Vol. 10, no. 2, pp. 353363, 2006. Regular paper.
Abstract Let G=(V,E) be a graph with n vertices and
let P be a set of n points in the plane.
We show that deciding whether there is a
planar straightline embedding of G such that the vertices V
are embedded onto the points P
is NPcomplete, even when G is 2connected and 2outerplanar.
This settles an open problem posed in [,,].
