The Straight-Line RAC Drawing Problem is NP-Hard

Evmorfia Argyriou; Michael Bekos; Antonios Symvonis

doi:10.7155/jgaa.00274

The Straight-Line RAC Drawing Problem is NP-Hard

Authors

Evmorfia Argyriou
Michael Bekos
Antonios Symvonis

DOI:

https://doi.org/10.7155/jgaa.00274

Keywords:

graph drawing , RAC graph , straight-line drawing , NP-hardness

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.

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2012-01-01

How to Cite

Argyriou, E., Bekos, M., & Symvonis, A. (2012). The Straight-Line RAC Drawing Problem is NP-Hard. Journal of Graph Algorithms and Applications, 16(2), 569–597. https://doi.org/10.7155/jgaa.00274