RAC-Drawability is ∃ℝ-complete and Related Results

Authors

  • Marcus Schaefer

DOI:

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

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.

Downloads

Download data is not yet available.

Downloads

Published

2024-03-16

How to Cite

Schaefer, M. (2024). RAC-Drawability is ∃ℝ-complete and Related Results. Journal of Graph Algorithms and Applications, 27(9), 803–841. https://doi.org/10.7155/jgaa.00646

Issue

Section

Articles

Categories