The quality of an embedding \(\Phi: V \mapsto \mathbb{R}2\) of a graph \(G = (V, E)\) into the Euclidean plane is the ratio of \(\max_{{u, v} \in E} |\Phi(u) - \Phi(v)|\) to \(\min_{{u, v} \not\in E} |\Phi(u) - \Phi(v)|\). This talk will focus on the problem of producing a “good” quality embedding of a given unit disk graph (UDG). Any UDG, by definition, has an embedding with quality less than 1. We present a polynomial time algorithm that computes a \(O(\log^{2.5} n)\)-quality embedding of a given UDG. A key step of this algorithm is the construction of a “growth-restricted approximation” of the given UDG.
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.