Shortest Path Separators in Unit Disk Graphs

Elfarouk Harb, Zhengcheng Huang, Da Wei Zheng

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.

Illustration of the crominating property: if a UDG edge (purple) crosses a Delaunay edge (black), its endpoints are within the 1-hop neighborhood of the Delaunay edge's endpoints.

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.

The perturbation technique used to create a planar backbone from pseudo-shortest paths, facilitating the application of planar separator theorems.

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

Abstract

We introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answers an open problem of Yan, Xiang and Dragan [CGTA ’12] and improves their result that requires removing the 3-hop neighbourhood of two shortest paths. Our proof uses very different ideas, including Delaunay triangulations and a generalization of the celebrated balanced separator theorem of Lipton and Tarjan [J. Appl. Math. ’79] to systems of non-intersecting paths.
BibTeX
@inproceedings{harb2024shortest,
  author = {Elfarouk Harb and Zhengcheng Huang and Da Wei Zheng},
  title = {{Shortest Path Separators in Unit Disk Graphs}},
  booktitle = {The European Symposium on Algorithms (ESA )},
  year = {2024},
  url = {https://openreview.net/forum?id=IOFebbEnek},
}
Figure