Unit disk graph approximation

Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical impor-tance in a variety of fields. In wireless ad hoc and sensor networks, such an embedding can be used to obtain virtual coordinates. In this paper, we prove a non-approximability result for the problem of embedding a given unit disk graph. Particularly, we show that if non-neighboring nodes are not allowed to be closer to each other than distance 1, then two neighbors can be as far apart as 3/2 − , where goes to 0 as n goes to infinity, unless P = NP. We further show that finding a realization of a d-quasi unit disk graph with d ≥ 1/√2 is NP-hard