The Straight-Line RAC Drawing Problem is NP-Hard
Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis · Journal of Graph Algorithms and Applications · 2012
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.