Good Quality Virtual Realization of Unit Disk Graphs

The quality of an embedding Φ: V 7 → R2 of a graph G = (V,E) into the Euclidean plane is the ratio of max{u,v}∈E ||Φ(u) − Φ(v)||2 to min{u,v}6∈E ||Φ(u) − Φ(v)||2. Given a graph G = (V,E), that is known to be a unit disk graph (UDG), we seek algorithms to compute an embedding Φ: V 7 → R2 of best (smallest) quality. Note that G comes with no associated geometric information and in this setting, related problems such as recognizing if G is a UDG, are NP-hard. While any UDG has a 2-dimensional embedding with quality between 1/2 and 1, the adaptation of Vempala’s random projection approach [37] by Kuhn et al. [21] provides the best quality bound of O(log3.5 n · √log logn). This paper presents a simple, combinatorial algorithm for computing a O(log3 n)-quality 2-dimensional embedding of a given graph, that is known to be a UDG. If the embedding is allowed to reside in higher dimensional space, we obtain improved results: a quality-2 embedding in R O(1). Our key technical contribution is the construction of a “growth-restricted approximation” of the given UDG. Construction of a growth-restricted approximation permits us to bypass the standard and costly technique of solving a linear program with exponentially many “spreading constraints. ” As a side effect of our construction, we get the first constant-factor approximation to the minimum clique partition problem for UDGs, given without a geometric representation. Our problem is a version of the well known localization problem in wireless sensor networks, in which network nodes are required to compute virtual 2-dimensional Euclidean coordinates given little or (as in our case) no geometric information