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. 421-446, 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 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.
This work is licensed under the terms of the CC-BY 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
|