MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 added 160 characters in body

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.) Though, as Dylan just explained, when the graph is "dense" enough to be universally rigid, then there is an efficient algorithm for (approximate) localization.
show/hide this revision's text 2 deleted 343 characters in body

Condions

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

There is a stronger property than global rigidity called "universal rigidity". This means that there is only one embedding (mod Eucl)consistent with the given distances in ANY dimension. For such graphs, one can (approximately) find the embedding in polynomial time using semi-definite programming. I do not know if your graphs will have this property.
show/hide this revision's text 1

Condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

There is a stronger property than global rigidity called "universal rigidity". This means that there is only one embedding (mod Eucl) consistent with the given distances in ANY dimension. For such graphs, one can (approximately) find the embedding in polynomial time using semi-definite programming. I do not know if your graphs will have this property.