The quality of an embedding F: V ? ? R 2 of a graph G = (V, E) into the Euclidean plane is the ratio of max{u,v}?E ||F(u) - F(v)||2 to min{u,v}??E ||F(u) - F(v)||2. Given a graph G = (V, E), that is known to be a unit ball graph in fixed dimensional Euclidean space R d, we seek algorithms to compute an embedding F: V ? ? R 2 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 unit disk graph (UDG), are NP-hard.

By Jeremy Yan. The unit ball random geometric graph $G=G^d_p(\lambda,n)$ has as its vertices $n$ points distributed independently and uniformly in the $d$-dimensional unit ball, with two vertices adjacent if and only if their $l_p$-distance is at