Geodesic
RAC-Drawability is ∃ℝ-complete and Related Results
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 9, pp. 803-841.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2023_27_9_a3,
     author = {Marcus Schaefer},
     title = {RAC-Drawability is {\ensuremath{\exists}\ensuremath{\mathbb{R}}-complete} and {Related} {Results}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {803--841},
     publisher = {mathdoc},
     volume = {27},
     number = {9},
     year = {2023},
     doi = {10.7155/jgaa.00646},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00646/}
}
TY  - JOUR
AU  - Marcus Schaefer
TI  - RAC-Drawability is ∃ℝ-complete and Related Results
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 803
EP  - 841
VL  - 27
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00646/
DO  - 10.7155/jgaa.00646
LA  - en
ID  - JGAA_2023_27_9_a3
ER  - 
%0 Journal Article
%A Marcus Schaefer
%T RAC-Drawability is ∃ℝ-complete and Related Results
%J Journal of Graph Algorithms and Applications
%D 2023
%P 803-841
%V 27
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00646/
%R 10.7155/jgaa.00646
%G en
%F JGAA_2023_27_9_a3
Marcus Schaefer. RAC-Drawability is ∃ℝ-complete and Related Results. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 9, pp. 803-841. doi : 10.7155/jgaa.00646. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00646/

Cité par Sources :