Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00548
Complexity of Geometric kPlanarity for Fixed k
Marcus Schaefer
Vol. 25, no. 1, pp. 2941, 2021. Regular paper.
Abstract The rectilinear local crossing number, $\mathop{\overline{\rm lcr}}(G)$, of a graph $G$ is the smallest $k$ so that $G$ has a straightline drawing with at most $k$ crossings along each edge. We show that deciding whether $\mathop{\overline{\rm lcr}}(G) \leq k$ for a fixed $k$ is complete for the existential theory of the reals, $\exists \mathbb{R}$.
This work is licensed under the terms of the CCBY license.

Submitted: August 2020.
Reviewed: January 2021.
Revised: January 2021.
Accepted: January 2021.
Final: January 2021.
Published: January 2021.
Communicated by
Giuseppe Liotta
