Abstract
This paper resolves a long-standing open problem in computational geometry by establishing that determining the geometric thickness of a multigraph is $\exists\mathbb{R}$-complete for any thickness $t \ge 30$. This classification places the problem in a complexity class between NP and PSPACE, characterizing it by the difficulty of finding real roots for multivariate polynomials.
Introduction
In graph theory, the concept of "thickness" refers to the minimum number of planar subgraphs required to cover all edges of a given graph. Geometric thickness introduces a more stringent geometric constraint: it requires a single straight-line drawing of the graph in the plane such that the edges can be partitioned into $t$ color classes, where no two edges of the same color intersect.
A practical analogy for this problem is an airline flight network. If cities are fixed points and flight paths are straight lines, geometric thickness asks for the minimum number of distinct altitudes (colors) needed so that no two flights at the same altitude cross paths. While determining if a graph has geometric thickness $t=2$ was previously known to be NP-hard, the complexity for higher values remained an open question until now.
Methodology
The authors prove $\exists\mathbb{R}$-completeness through a sophisticated reduction chain starting from the Existential Theory of the Reals ($\exists\mathbb{R}$).
- The Reduction Chain: The proof proceeds from $\exists\mathbb{R}$ to "Strict Inequality" problems, then to "Pseudo-Segment Stretchability," and finally to "Geometric Thickness."
- Gadget Engineering: To translate abstract algebraic constraints into geometric structures, the authors utilize "Von Staudt gadgets"—which represent arithmetic operations like addition and multiplication through geometric intersections—and "transmission gadgets" to propagate information across the graph.
- Chromatic Optimization: A critical component of the proof involves demonstrating that the arrangements of pseudo-segments used in the reduction can be colored with a relatively small number of colors (specifically 30). This optimization allows the authors to fix the thickness threshold for $\exists\mathbb{R}$-completeness at $t=30$.
Key Insights
- Algebraic Nature: The most significant insight is that geometric thickness is fundamentally algebraic rather than purely combinatorial. The positions of vertices may require "wild" real coordinates that cannot be represented as simple fractions, placing the problem firmly within the $\exists\mathbb{R}$ class.
- The Role of Multigraphs: By focusing on multigraphs (graphs allowing multiple edges between the same pair of vertices), the authors can more effectively "force" specific geometric configurations required for the reduction gadgets.
- Sunflower SGE: The research also extends to Simultaneous Graph Embedding (SGE). The authors prove that even in the "empty sunflower" case—where graphs share vertices but have entirely disjoint edge sets—the problem remains $\exists\mathbb{R}$-complete for $k=31$ graphs.
Key Results
- Main Theorem: Geometric Thickness is $\exists\mathbb{R}$-complete for multigraphs for any fixed thickness $t \ge 30$.
- Planarity Bound: The problem remains $\exists\mathbb{R}$-complete even for 4392-planar graphs (where each edge crosses at most 4392 others in a topological drawing).
- SGE Complexity: Simultaneous Graph Embedding of 31 edge-disjoint graphs is $\exists\mathbb{R}$-complete.
Conclusion and Future Work
This work pinpoints the exact complexity of geometric thickness for multigraphs, highlighting the deep connection between graph drawing and the existential theory of the reals. While the bound of $t=30$ is a major achievement, future work remains to bridge the gap between $t=2$ and $t=30$, and to extend these results to simple graphs. Additionally, the potential for exponentially large coordinates in these drawings poses ongoing challenges for practical grid-based representations.
Summary updated