Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical importance 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.
展开▼
