Geodesic
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) no. 2, pp. 353-363.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 [,,]. 
@article{JGAA_2006_10_2_a12,
     author = {Sergio Cabello},
     title = {Planar embeddability of the vertices of a graph using a fixed point set is {NP-hard}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {353--363},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00132},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00132/}
}
TY  - JOUR
AU  - Sergio Cabello
TI  - Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 353
EP  - 363
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00132/
DO  - 10.7155/jgaa.00132
LA  - en
ID  - JGAA_2006_10_2_a12
ER  - 
%0 Journal Article
%A Sergio Cabello
%T Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
%J Journal of Graph Algorithms and Applications
%D 2006
%P 353-363
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00132/
%R 10.7155/jgaa.00132
%G en
%F JGAA_2006_10_2_a12
Sergio Cabello. 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) no. 2, pp. 353-363. doi : 10.7155/jgaa.00132. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00132/

Cité par Sources :