The Complexity of Drawing a Graph in a Polygonal Region

Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal

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. A special case is the problem of extending a partial planar graph drawing, which was proved NP-hard by Patrignani. 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 for 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 be bounded in the special case of a convex region, or for drawing a path in any polygonal region.
BibTeX
@inproceedings{lubiw2018complexity,
  author = {Anna Lubiw and Tillmann Miltzow and Debajyoti Mondal},
  title = {{The Complexity of Drawing a Graph in a Polygonal Region}},
  booktitle = {GD},
  year = {2018},
  doi = {10.1007/978-3-030-04414-5\_28},
}
Figure