Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00646
RACDrawability is ∃ℝcomplete and Related Results
Vol. 27, no. 9, pp. 803841, 2023. Regular paper.
Abstract A RACdrawing of a graph is a straightline drawing in which every crossing occurs at a right angle. We show that deciding whether a graph has a RACdrawing 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 (doublyexponentially so) to being right angles.
We also show that if a graph has a RACdrawing in which every edge has at most one bend, then such a drawing can be placed on an integer grid of doubleexponential area. This is in contrast to RACdrawability on the grid which turns out to be as hard as the existential theory of the rationals.
This work is licensed under the terms of the CCBY license.

Submitted: July 2022.
Reviewed: April 2023.
Revised: July 2023.
Accepted: November 2023.
Final: November 2023.
Published: December 2023.
Communicated by
Antonios Symvonis

Journal Supporters
