The Straight-Line RAC Drawing Problem is NP-Hard

Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis

Journal of Graph Algorithms and Applications · 2012 · 48 citations · 0 references

DOIFull text

Open access

Concepts

Abstract

Recent cognitive experiments have shown that the negative impact of an edgecrossing on the human understanding of a graph drawing, tends to be eliminatedin the case where the crossing angles are greater than 70 degrees. Thismotivated the study of RAC drawings, in which every pair of crossing edgesintersects at right angle. In this work, we demonstrate