Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00274 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 |