Sriram Pemmaraju, University of Iowa – “Geometric Embeddings of Unit Disk Graphs”

April 17, 2008 @ 10:45 am – 12:00 pm




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}
otin 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 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.

Back to top