Geodesic
The Straight-Line RAC Drawing Problem is NP-Hard
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 569-597.

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

A RAC drawing of a graph is a polyline drawing in which every pair of crossing edges intersects at right angle. In this paper, we focus on straight-line RAC drawings and demonstrate an infinite class of graphs with unique RAC combinatorial embedding. We employ members of this class in order to show that it is NP-hard to decide whether a graph admits a straight-line RAC drawing.
DOI : 10.7155/jgaa.00274
Keywords: graph drawing, RAC graph, straight-line drawing, NP-hardness 
@article{JGAA_2012_16_2_a16,
     author = {Evmorfia Argyriou and Michael Bekos and Antonios Symvonis},
     title = {The {Straight-Line} {RAC} {Drawing} {Problem} is {NP-Hard}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {569--597},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00274},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00274/}
}
TY  - JOUR
AU  - Evmorfia Argyriou
AU  - Michael Bekos
AU  - Antonios Symvonis
TI  - The Straight-Line RAC Drawing Problem is NP-Hard
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 569
EP  - 597
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00274/
DO  - 10.7155/jgaa.00274
LA  - en
ID  - JGAA_2012_16_2_a16
ER  - 
%0 Journal Article
%A Evmorfia Argyriou
%A Michael Bekos
%A Antonios Symvonis
%T The Straight-Line RAC Drawing Problem is NP-Hard
%J Journal of Graph Algorithms and Applications
%D 2012
%P 569-597
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00274/
%R 10.7155/jgaa.00274
%G en
%F JGAA_2012_16_2_a16
Evmorfia Argyriou; Michael Bekos; Antonios Symvonis. The Straight-Line RAC Drawing Problem is NP-Hard. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 569-597. doi : 10.7155/jgaa.00274. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00274/

Cité par Sources :