Return to Answer

Image link broken; now fixed. Added a reference while fixing the link.

Source Link

edited Apr 29, 2017 at 19:24

150.8k
36
358
958

This is not a direct answer, but rather an historical, and somewhat tangential comment. Way backBack in 1979, the general problem you posed was proved NP-hard by Saxe and by Yemini independently. There has been quite a rich literature on this topic in the last 30+35+ years, which you might trace via Google Scholar. Added. For example, see the 2014 survey below.

[Sax79] James B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979. Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980. (PDF download.)

[Yem79] Yechiam Yemini. Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979. DOI: 10.1109/SFCS.1979.39 (ACM link.)

Liberti, Leo, Carlile Lavor, Nelson Maculan, and Antonio Mucherino. "Euclidean distance geometry and applications." Siam Review 56(1) (2014): 3-69. (Journal link.)

H16 http://cs.smith.edu/~orourke/MathOverflow/H16.png H16

_{(Figure from "Untangling planar graphs from a specified vertex position—Hard cases" ([Elsevier link][3]).)}

This is not a direct answer, but rather an historical, and somewhat tangential comment. Way back in 1979, the general problem you posed was proved NP-hard by Saxe and by Yemini independently. There has been quite a rich literature on this topic in the last 30+ years, which you might trace via Google Scholar.

[Sax79] James B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979. Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980. (PDF download)

[Yem79] Yechiam Yemini. Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979. DOI: 10.1109/SFCS.1979.39 (ACM link)

H16 http://cs.smith.edu/~orourke/MathOverflow/H16.png
_{(Figure from "Untangling planar graphs from a specified vertex position—Hard cases" ([Elsevier link][3]).)}

This is not a direct answer, but rather an historical, and somewhat tangential comment. Back in 1979, the general problem you posed was proved NP-hard by Saxe and by Yemini independently. There has been quite a rich literature on this topic in the last 35+ years, which you might trace via Google Scholar. Added. For example, see the 2014 survey below.

James B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979. Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980. (PDF download.)

Yechiam Yemini. Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979. DOI: 10.1109/SFCS.1979.39 (ACM link.)