TY - JOUR

T1 - The Complexity of Drawing a Graph in a Polygonal Region

AU - Lubiw, Anna

AU - Miltzow, Till

AU - Mondal, Debajyoti

N1 - Funding Information:
Acknowledgment. We would like to thank Günter Rote, who discussed with the second author the turn gadget in the context of the Art Gallery Problem. We are also grateful to the anonymous reviewers for all their many helpful suggestions. The research of the second author is in part generously supported by ERC Consolidator Grant 615640-ForEFront and the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Research of the first and third authors is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
Publisher Copyright:
© 2022, Brown University. All rights reserved.

PY - 2022/7

Y1 - 2022/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85135757469&partnerID=8YFLogxK

U2 - 10.7155/jgaa.00602

DO - 10.7155/jgaa.00602

M3 - Article

SN - 1526-1719

VL - 26

SP - 421

EP - 446

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 4

M1 - 4

ER -