Shortest Path Separators in Unit Disk Graphs
Introduction
Balanced separators are fundamental tools in graph theory, enabling efficient divide-and-conquer algorithms. While planar graphs possess well-defined separator properties, Unit Disk Graphs (UDGs)—where vertices are represented by disks in a plane and edges exist between overlapping disks—present greater challenges due to potential edge crossings. This paper presents a breakthrough in UDG theory by proving a new balanced separator theorem based on the 1-hop neighborhood of shortest paths.
The Problem: Beyond Planarity
A separator is a set of vertices whose removal partitions a graph into smaller, balanced components. In UDGs, previous work by Yan et al. (2012) established that separators could be formed using the 3-hop neighborhood of two shortest paths. The question remained: could this be tightened? This research proves that a 1-hop neighborhood is sufficient, reaching the theoretical lower bound, as dense UDGs like cliques cannot be separated by paths alone (0-hop).
Methodology: Bridging Geometry and Graph Theory
The authors avoid direct manipulation of the UDG's intersection graph, which can be highly non-planar. Instead, they utilize a geometric backbone: the Delaunay Triangulation (DT) of the disk centers.
The "Crominating" Property
A key insight is the "crominating" (cross-dominating) property of Delaunay edges. The authors prove that if a UDG edge crosses a Delaunay edge, at least one of its endpoints must be a neighbor of the Delaunay edge's endpoints. This property allows the planar structure of the DT to inform the connectivity of the UDG.
Pseudo-shortest Paths and Perturbation
The algorithm constructs a system of "pseudo-shortest" paths using Delaunay edges. While these paths are not strictly the shortest in the UDG, they remain geometrically close to them. To apply planar separator theorems (like Lipton-Tarjan) to this non-planar graph, the authors use a perturbation technique. They "split" vertices involved in multiple paths to create a temporary planar structure, allowing for the identification of a Jordan curve that serves as the balanced separator.
Key Results
The primary contribution is the proof that every UDG admits a shortest path 1-neighborhood separator. This separator consists of the 1-hop neighbors of two shortest paths and two additional vertices. Furthermore, the authors provide a constructive $O(n^2)$ time algorithm to find such a separator. This result is qualitatively optimal; the 1-hop requirement is the minimum possible for general UDGs.
Conclusion and Future Directions
This work settles a decade-old open problem by demonstrating that the influence of shortest paths in UDGs is more localized than previously assumed. Future research may focus on improving the $O(n^2)$ runtime to match the near-linear performance of planar separators or generalizing these findings to other geometric intersection graphs, such as those involving disks of varying sizes.
Summary updated