Collective Tree Spanners for Unit Disk Graphs with Applications

In this paper, we establish a novel balanced separator theorem for Unit Disk Graphs (UDGs), which mimics the well-known Lipton and Tarjan's planar balanced shortest paths separator theorem. We prove that, in any n-vertex UDG G, one can find two hop-shortest paths P(s,x) and P(s,y) such that the removal of the 3-hop-neighborhood of these paths (i.e., ) from G leaves no connected component with more than 2/3n vertices. This new balanced shortest-paths—3- hop-neighborhood separator theorem allows us to build, for any n-vertex UDG G, a system T(G) of at most spanning trees of G such that, for any two vertices x and y of G, there exists a tree T in T(G) with dT(x,y)⩽3⋅dG(x,y)+12. That is, the distances in any UDG can be approximately represented by the distances in at most of its spanning trees. Using these results, we propose a new compact and low delay routing labeling scheme for UDGs.