# The Complexity of Drawing a Graph in a Polygonal Region

arXiv: https://arxiv.org/abs/1802.06699 · HTML: https://mlsanity.com/paper/1802.06699/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2018.

## Built on by (most cited first, 4 of 4)

- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [On Classifying Continuous Constraint Satisfaction Problems](https://mlsanity.com/paper/2106.02397/) (2021)
- [Covering Polygons is Even Harder](https://mlsanity.com/paper/2106.02335/) (2021)
- [Training Neural Networks is existsmathbb R-complete](https://mlsanity.com/paper/2102.09798/) (2021)

## Abstract (arXiv)

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 strengthens an 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 be bounded in the special case of a convex region, or for drawing a path in any polygonal region.