RAC-drawability is \(\exists \mathbb{R} \)-complete

DOI10.1007/978-3-030-92931-2_5OpenAlexW4206038921MaRDI QIDQ2151432

Marcus Schaefer

Publication date: 1 July 2022

Full work available at URL: https://arxiv.org/abs/2107.11663

zbMATH Keywords

computational complexitystraight-line drawingexistential theory of the realsRAC-drawingright-angle drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The Complexity of Angular Resolution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing and drawing IC-planar graphs
• Graphs that admit right angle crossing drawings
• Drawing graphs with right angle crossings
• Mnëv's universality theorem revisited
• On RAC drawings of 1-planar graphs
• Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph
• The Straight-Line RAC Drawing Problem is NP-Hard
• Right Angle Crossing Drawings of Graphs
• Complexity of Geometric k-Planarity for Fixed k
• Recognizing Visibility Graphs of Triangulated Irregular Networks
• On the Complexity of Some Geometric Problems With Fixed Parameters
• On the Perspectives Opened by Right Angle Crossing Drawings
• Drawing Partially Embedded and Simultaneously Planar Graphs