Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
The Straight-Line RAC Drawing Problem is NP-Hard
Evmorfia N. Argyriou , Michael A. Bekos , and Antonios Symvonis
Vol. 16, no. 2, pp. 569-597, 2012. Regular paper
Abstract 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.
Submitted: October 2011.
Reviewed: March 2012.
Revised: April 2012.
Accepted: August 2012.
Final: August 2012.
Published: September 2012.
Communicated by Seok-Hee Hong
|Journal of Graph Algorithms and Applications|