Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00274
The Straight-Line RAC Drawing Problem is NP-Hard
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
article (PDF)
BibTeX