Geodesic
The Complexity of Drawing a Graph in a Polygonal Region
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 421-446.

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

We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to points on the boundary of the region, place the remaining vertices to create a planar straight-line drawing of the graph inside the region. This establishes a wider context for the NP-hardness result by Patrignani on extending partial planar graph drawings. Our result is one of the first showing that a problem of drawing planar graphs with straight-line edges is hard for the existential theory of the reals. The complexity of the problem is open in the case of a simply connected region. We also show that, even for integer input coordinates, it is possible that drawing a graph in a polygonal region requires some vertices to be placed at irrational coordinates. By contrast, the coordinates are known to have bounded bit complexity for the special case of a convex region, or for drawing a path in any polygonal region. In addition, we prove a Mnëv-type universality result - loosely speaking, that the solution spaces of instances of our graph drawing problem are equivalent, in a topological and algebraic sense, to bounded algebraic varieties. 
@article{JGAA_2022_26_4_a1,
     author = {Anna Lubiw and Tillmann Miltzow and Debajyoti Mondal},
     title = {The {Complexity} of {Drawing} a {Graph} in a {Polygonal} {Region}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {421--446},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00602},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00602/}
}
TY  - JOUR
AU  - Anna Lubiw
AU  - Tillmann Miltzow
AU  - Debajyoti Mondal
TI  - The Complexity of Drawing a Graph in a Polygonal Region
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 421
EP  - 446
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00602/
DO  - 10.7155/jgaa.00602
LA  - en
ID  - JGAA_2022_26_4_a1
ER  - 
%0 Journal Article
%A Anna Lubiw
%A Tillmann Miltzow
%A Debajyoti Mondal
%T The Complexity of Drawing a Graph in a Polygonal Region
%J Journal of Graph Algorithms and Applications
%D 2022
%P 421-446
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00602/
%R 10.7155/jgaa.00602
%G en
%F JGAA_2022_26_4_a1
Anna Lubiw; Tillmann Miltzow; Debajyoti Mondal. The Complexity of Drawing a Graph in a Polygonal Region. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 421-446. doi : 10.7155/jgaa.00602. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00602/

Cité par Sources :