At first glance, computational geometry and graph theory inhabit different worlds. Geometry deals with continuous space, coordinates, and distances, while graph theory focuses on discrete relationships and connectivity. However, a powerful research direction has emerged that treats these two domains as interchangeable. By reducing geometric problems to graph-theoretic ones—or vice versa—researchers can unlock efficient algorithms for spatial tasks and prove the inherent difficulty of geometric optimizations.
Geometry as a Constraint Graph
The most intuitive application of this duality is representing geometric constraints as graph edges. In this view, a spatial problem is solved not by moving objects in space, but by selecting nodes in a graph that satisfy specific relational rules.
For example, in the domain of automated design, Xu et al. tackle the NP-complete 2D tiling problem by reformulating it as a node-selection task. They construct a graph where each node represents a candidate tile placement. Edges encode physical constraints: some edges represent "conflicts" (overlapping tiles), while others represent "ideal placements" (perfect edge-to-edge contact). By training a Graph Neural Network on this structure, the authors can solve complex tiling tasks significantly faster than traditional combinatorial solvers.
A similar logic applies to polygon decomposition. Nusser et al. solve the problem of covering a polygon with the minimum number of convex pieces by building a visibility graph. Here, geometric units are vertices, and an edge exists if the convex hull of two units remains within the polygon. This reduction allows them to use vertex clique cover algorithms to identify the best regions to merge, winning the CG:SHOP 2023 Challenge. Even in knot theory, Fiedler shows that the isotopy of links in a torus can be mapped to the evolution of "trace graphs," shifting the complexity from algebraic topology to combinatorial graph analysis.
Proving Hardness through Geometric Mapping
While reductions often help find solutions, they are equally vital for proving that a solution is hard to find. To prove a geometric problem is NP-hard, researchers often map a known hard graph problem (like Vertex Cover or Independent Set) into a geometric configuration.
In the study of clustering, Awasthi et al. and Lee et al. established the inapproximability of $k$-means clustering by embedding graphs into high-dimensional Euclidean space. They assigned each graph vertex a unique unit basis vector and represented each edge as a point at the sum of its incident vertex vectors. This construction ensures that the optimal way to cluster these "edge points" is to select cluster centers that correspond to a minimum Vertex Cover in the original graph. Schmidt et al. later simplified this framework, providing a clear geometric interpretation of how vertex cover constraints mirror the $k$-means objective.
This technique extends to point set topology and transformations:
- General Position: Froese et al. proved that finding the largest subset of points where no three are collinear is NP-hard by using collinearity to mimic graph adjacency.
- Triangulation Flips: Lubiw and Pathak showed that calculating the "flip distance" between two triangulations is NP-complete by mapping the Vertex Cover problem onto geometric configurations where "shortcuts" in the flip sequence correspond to vertex selections.
Exploiting Structural Duality for Efficiency
When a graph is derived from geometry, it often inherits special structural properties that general graphs lack. Recognizing these properties allows for the use of specialized algorithms that are much faster than their general-purpose counterparts.
A recurring theme is the reduction to bipartite matching. Chen et al. demonstrated that the problem of moving points to form a regular $n$-gon can be solved via maximum matching in a bipartite graph derived from distance constraints. Similarly, Ma et al. showed that spatial optimization over discrete color sets can be abstracted into a graph where colors are vertices, reducing the problem size from the number of points to the number of colors.
In the case of Unit-Disk Graphs (where edges exist between points within a fixed distance), the geometry provides a "cobipartite" structure in certain configurations. Tkachenko et al. and Afshani leveraged this to solve the Maximum Clique problem. By covering the potential solution space with geometric shapes, they transform the search for a clique into a search for a maximum independent set in a bipartite graph, which is computationally efficient.
Finally, the reduction can work in reverse to speed up graph problems. Biedl and Gokhale showed that finding maximum matchings in RDV graphs can be reduced to a geometric query problem, specifically orthogonal ray shooting. By using dynamic geometric data structures, they achieved near-linear time complexity, demonstrating that the bridge between graphs and geometry is a two-way street for algorithmic innovation.
Key Foundational Work
Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs (2005) — contributed 1 concept elements to this direction.
A one-parameter approach to knot theory (2006) — contributed 1 concept elements to this direction.