Geodesic
Complexity of Geometric k-Planarity for Fixed k
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 29-41.

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

The rectilinear local crossing number, $\mathop{\overline{\rm lcr}}(G)$, of a graph $G$ is the smallest $k$ so that $G$ has a straight-line 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}$.
DOI : 10.7155/jgaa.00548
Keywords: local crossing number, rectilinear crossing number, rectilinear local crossing number, existential theory of the reals, computational complexity 
@article{JGAA_2021_25_1_a1,
     author = {Marcus Schaefer},
     title = {Complexity of {Geometric} {k-Planarity} for {Fixed} k},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {29--41},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00548},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00548/}
}
TY  - JOUR
AU  - Marcus Schaefer
TI  - Complexity of Geometric k-Planarity for Fixed k
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 29
EP  - 41
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00548/
DO  - 10.7155/jgaa.00548
LA  - en
ID  - JGAA_2021_25_1_a1
ER  - 
%0 Journal Article
%A Marcus Schaefer
%T Complexity of Geometric k-Planarity for Fixed k
%J Journal of Graph Algorithms and Applications
%D 2021
%P 29-41
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00548/
%R 10.7155/jgaa.00548
%G en
%F JGAA_2021_25_1_a1
Marcus Schaefer. Complexity of Geometric k-Planarity for Fixed k. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 29-41. doi : 10.7155/jgaa.00548. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00548/

Cité par Sources :