In graph theory, we often ask if an abstract set of connections can be "realized" in physical space. Can a graph be drawn without edges crossing? Can it be represented as the intersection pattern of unit disks, straight line segments, or convex polygons? While these questions feel intuitive, they hide a deep hierarchy of computational complexity.
Research in this area focuses on mapping the boundary between problems that are efficiently solvable and those that are fundamentally intractable, often requiring a complexity class beyond NP: the Existential Theory of the Reals ($\exists\mathbb{R}$).
The Real-World Barrier of $\exists\mathbb{R}$
Most computer science students are familiar with NP-completeness—problems where a solution is hard to find but easy to verify. However, many geometric problems are even harder. When we try to represent a graph using geometric objects, we aren't just making discrete choices; we are looking for real-valued coordinates that satisfy a system of polynomial inequalities.
Michael Gene Dobbins, Andreas F. Holmsen, and Tillmann Miltzow demonstrated this in A Universality Theorem for Nested Polytopes, proving that nesting one polytope inside another is $\exists\mathbb{R}$-complete. This means the problem is as hard as deciding if any system of polynomial equations has a real solution.
This complexity appears across the geometric spectrum. Michael M. Hoffmann and Tillmann Miltzow recently settled long-standing questions by proving that recognizing unit segment and polyline graphs is also $\exists\mathbb{R}$-complete. Similarly, Nicholas Bieker and Emil Dohse showed that even moving to hyperbolic geometry does not escape this complexity for unit disk graphs. The intuition here is that geometric constraints can "force" coordinates to be irrational or require exponential precision, making them impossible to verify with a simple discrete certificate.
The Fragility of Planarity
Even when we stick to simple drawings in the plane, complexity arises the moment we allow for imperfection. While testing if a graph is perfectly planar is easy, minimizing the number of edge crossings is notoriously difficult.
Jan Kratochvíl established early on that recognizing disk intersection graphs is NP-hard. More recently, Liana Khazaliya and Petr Hliněný proved that the crossing number problem remains NP-hard even for graphs with very simple structures, like those with low path-width.
The difficulty isn't just in creating a drawing from scratch, but in modifying existing ones. Robert Ganian and colleagues have shown that extending a partial drawing by adding even a single edge while minimizing crossings is NP-hard. This suggests that "untangling" a graph is a global problem; local adjustments rarely suffice to reach an optimal state.
Finding Islands of Tractability
To combat this widespread intractability, researchers look for "islands of tractability"—specific conditions where these problems become solvable. One primary tool is Fixed-Parameter Tractability (FPT).
For example, while the general crossing number problem is hard, Martin Grohe proved that if we fix the number of allowed crossings $k$, the problem can be solved in quadratic time. Similarly, Sujoy Bhore and Martin Nöllenburg demonstrated that extending orthogonal drawings is FPT when the size of the new subgraph is small.
Another strategy involves restricting the "style" of the drawing. Seok-Hee Hong and Peter Eades developed a linear-time algorithm for outer-1-planar graphs, where all vertices must touch the outer boundary and each edge crosses at most one other. By imposing these rigid structural constraints, the vast search space of possible drawings collapses into a manageable combinatorial structure.
The Tractability Cliff
Recent work by Meirav Zehavi and Fedor V. Fomin on layered crossing minimization highlights what they call a "tractability cliff." In hierarchical drawings, they found that while 3-layer drawings allow for subexponential algorithms, adding just a few more layers makes the problem significantly harder.
This pattern repeats across the field: a small amount of flexibility (like allowing one crossing per edge or a few extra layers) often transforms a simple problem into one that is NP-hard or $\exists\mathbb{R}$-complete. The goal of current research is to precisely locate these cliffs, helping us understand which geometric constraints are "free" and which ones carry a heavy computational price.