The Complexity of Drawing a Graph in a Polygonal Region

Authors

  • Anna Lubiw
  • Tillmann Miltzow
  • Debajyoti Mondal

DOI:

https://doi.org/10.7155/jgaa.00602

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.

Downloads

Download data is not yet available.

Downloads

Published

2022-07-01

How to Cite

Lubiw, A., Miltzow, T., & Mondal, D. (2022). The Complexity of Drawing a Graph in a Polygonal Region. Journal of Graph Algorithms and Applications, 26(4), 421–446. https://doi.org/10.7155/jgaa.00602

Issue

Section

Articles

Categories