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
|
Journal Supporters
|