Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00646
RAC-Drawability is ∃ℝ-complete and Related Results
Vol. 27, no. 9, pp. 803-841, 2023. Regular paper.
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.
 This work is licensed under the terms of the CC-BY license.
Submitted: July 2022.
Reviewed: April 2023.
Revised: July 2023.
Accepted: November 2023.
Final: November 2023.
Published: December 2023.
Communicated by Antonios Symvonis
article (PDF)
BibTeX