April 17, 2008 - Sriram Pemmaraju

Title: Geometric Embeddings of Unit Disk Graphs

Abstract:
The \textit{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 \textit{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 {\em 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.