Geodesic
The Complexity of Angular Resolution
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 7, pp. 565-580.

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

The angular resolution of a straight-line drawing of a graph is the smallest angle formed by any two edges incident to a vertex. The angular resolution of a graph is the supremum of the angular resolutions of all straight-line drawings of the graph. We show that testing whether a graph has angular resolution at least $\pi/(2k)$ is complete for $\exists\mathbb{R}$, the existential theory of the reals, for every fixed $k \geq 2$. This remains true if the graph is planar and a plane embedding of the graph is fixed. 
@article{JGAA_2023_27_7_a2,
     author = {Marcus Schaefer},
     title = {The {Complexity} of {Angular} {Resolution}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {565--580},
     publisher = {mathdoc},
     volume = {27},
     number = {7},
     year = {2023},
     doi = {10.7155/jgaa.00634},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00634/}
}
TY  - JOUR
AU  - Marcus Schaefer
TI  - The Complexity of Angular Resolution
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 565
EP  - 580
VL  - 27
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00634/
DO  - 10.7155/jgaa.00634
LA  - en
ID  - JGAA_2023_27_7_a2
ER  - 
%0 Journal Article
%A Marcus Schaefer
%T The Complexity of Angular Resolution
%J Journal of Graph Algorithms and Applications
%D 2023
%P 565-580
%V 27
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00634/
%R 10.7155/jgaa.00634
%G en
%F JGAA_2023_27_7_a2
Marcus Schaefer. The Complexity of Angular Resolution. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 7, pp. 565-580. doi : 10.7155/jgaa.00634. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00634/

Cité par Sources :