The Complexity of Drawing a Graph in a Polygonal Region

Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal

Abstract

This research establishes that the problem of drawing a planar graph with straight lines inside a given polygonal region is $\exists\mathbb{R}$-complete. This classification implies the problem is not only NP-hard but also algebraically complex; specifically, valid drawings may require vertex coordinates to be irrational even when the input polygon is defined entirely by integers.

Introduction

In the field of graph drawing, Tutte’s 1963 theorem provides a polynomial-time algorithm for drawing planar graphs with straight edges inside convex polygons. However, real-world constraints often involve non-convex boundaries or regions with obstacles (holes). This paper investigates the Graph in Polygon problem: given a planar graph, a closed polygonal region (potentially with holes), and fixed positions for a subset of vertices on the boundary, can the remaining vertices be placed to create a valid straight-line planar drawing within the region?

Figure 1: An example of the Graph in Polygon problem, showing a straight-line drawing within a non-convex region containing a hole.

Complexity and the Challenge of Irrationality

A significant hurdle in classifying this problem was the "coordinate issue." While researchers previously suspected NP-hardness, proving membership in NP was difficult because representing vertex coordinates might require infinite precision. This paper formally addresses this by proving the problem is $\exists\mathbb{R}$-complete, placing it in the class of problems equivalent to deciding if a system of polynomial equations and inequalities has a real solution.

One of the most striking insights is that irrationality is unavoidable. The authors demonstrate that even if the input polygon and fixed vertices use simple integer coordinates, the only valid placement for the remaining vertices might require irrational numbers. This confirms that the problem cannot be in NP unless NP = $\exists\mathbb{R}$.

Methodology: Geometric Reductions

The authors prove $\exists\mathbb{R}$-hardness through a polynomial-time reduction from a planar variant of the Existential Theory of the Reals, specifically Planar-ETR-INV*. They translate algebraic constraints—such as $x + y = z$ and $x \cdot y = 1$—into geometric constraints using ingenious "gadgets."

Figure 5: The reduction process illustrating how abstract graph embeddings (a-d) are mapped to specific geometric constraints within a polygonal region (e).

In these gadgets, real-valued variables are represented by vertices constrained to lie on specific line segments. The authors utilize the polygon's boundaries and holes to force geometric relationships (such as those derived from Thales's theorem) that mirror algebraic operations. By interconnecting these gadgets into a single large graph and polygon, any valid drawing of the resulting instance effectively solves the underlying system of polynomial equations.

Key Results

  • Theorem 1 (Irrationality): There exist instances of the Graph in Polygon problem with integer coordinates where some vertices strictly require irrational coordinates to be drawn without intersections.
  • Theorem 2 (Main Result): The Graph in Polygon problem is $\exists\mathbb{R}$-complete.
  • Theorem 3 (Foundational Contribution): The algebraic problem Planar-ETR-INV* is shown to be $\exists\mathbb{R}$-complete, providing a highly useful technical tool for future researchers proving the complexity of other planar geometric problems.

Conclusion and Future Work

While this paper settles the complexity for general polygonal regions with holes, several open questions remain. The complexity for simple polygons (without holes) or for specific graph classes like trees remains unknown. Furthermore, the distinction between open and closed regions—where edges are either forbidden from or allowed to touch the boundary—presents a different set of challenges for future investigation.

Summary updated

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