Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00602
The Complexity of Drawing a Graph in a Polygonal Region
Anna Lubiw,
Tillmann Miltzow, and
Debajyoti Mondal
Vol. 26, no. 4, pp. 421446, 2022. Regular paper.
Abstract 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 straightline drawing of the graph inside the region.
This establishes a wider context for the NPhardness 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 straightline 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ëvtype 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.
This work is licensed under the terms of the CCBY license.

Submitted: April 2021.
Reviewed: May 2022.
Revised: June 2022.
Accepted: June 2022.
Final: July 2022.
Published: July 2022.
Communicated by
Alexander Wolff

Journal Supporters
