RAC-Drawability is ∃ℝ-complete and Related Results

Abstract

A RAC-drawing of a graph is a straight-line drawing in which every crossing occurs at a right angle. We show that deciding whether a graph has a RAC-drawing is as hard as the existential theory of the reals, even if we know that every edge is involved in at most eleven crossings and even if the drawing is specified up to isomorphism. The problem remains hard if the crossing angles are only required to be very close (doubly-exponentially so) to being right angles. We also show that if a graph has a RAC-drawing in which every edge has at most one bend, then such a drawing can be placed on an integer grid of double-exponential area. This is in contrast to RAC-drawability on the grid which turns out to be as hard as the existential theory of the rationals.