Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00132 Planar embeddability of the vertices of a graph using a fixed point set is NP-hard Sergio Cabello Vol. 10, no. 2, pp. 353-363, 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 straight-line embedding of G such that the vertices V are embedded onto the points P is NP-complete, even when G is 2-connected and 2-outerplanar. This settles an open problem posed in [,,].
|
Revised: June 2006. Submitted: July 2005. Communicated by Michael Goodrich |
| Journal of Graph Algorithms and Applications |