{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T15:36:40Z","timestamp":1768750600726,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T00:00:00Z","timestamp":1380067200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s00454-013-9545-6","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T01:19:02Z","timestamp":1380071942000},"page":"1051-1071","source":"Crossref","is-referenced-by-count":6,"title":["Constructing Uniquely Realizable Graphs"],"prefix":"10.1007","volume":"50","author":[{"given":"Igor","family":"Pak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,25]]},"reference":[{"key":"9545_CR1","unstructured":"Alfakih, A., Wolkowicz, H.: On the embeddability of weighted graphs in euclidean spaces. Research Report CORR 98\u201312. University of Waterloo, Waterloo (1998)"},{"key":"9545_CR2","doi-asserted-by":"crossref","first-page":"746","DOI":"10.1137\/S1052623496304700","volume":"8","author":"F Alizadeh","year":"1998","unstructured":"Alizadeh, F., Haeberly, J.-P., Overton, M.: Primal\u2013dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8, 746\u2013768 (1998)","journal-title":"SIAM J. Optim."},{"key":"9545_CR3","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N Alon","year":"1997","unstructured":"Alon, N., Kahale, N.A.: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26, 1733\u20131748 (1997)","journal-title":"SIAM J. Comput."},{"key":"9545_CR4","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1109\/TMC.2006.174","volume":"5","author":"J Aspnes","year":"2006","unstructured":"Aspnes, J., Eren, T., Goldenberg, D., Morse, A., Whiteley, W., Yang, Y., Anderson, B., Belhumeur, P.: A theory of network localization. IEEE Trans. Mobile Comput. 5, 1663\u20131678 (2006)","journal-title":"IEEE Trans. Mobile Comput."},{"key":"9545_CR5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02574037","volume":"13","author":"A Barvinok","year":"1995","unstructured":"Barvinok, A.: Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom. 13, 189\u2013202 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9545_CR6","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1142\/S0218195907002239","volume":"17","author":"M Boutin","year":"2007","unstructured":"Boutin, M., Kemper, G.: Which point configurations are determined by the distribution of their pairwise distances? Int. J. Comput. Geom. Appl. 17, 31\u201343 (2007)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9545_CR7","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1017\/S0963548306007917","volume":"16","author":"A Coja-Oghlan","year":"2007","unstructured":"Coja-Oghlan, A.: Coloring semirandom graphs. Combin. Probab. Comput. 16, 515\u2013552 (2007)","journal-title":"Combin. Probab. Comput."},{"key":"9545_CR8","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1017\/S0963548309990514","volume":"19","author":"A Coja-Oghlan","year":"2010","unstructured":"Coja-Oghlan, A.: Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput. 19, 227\u2013284 (2010)","journal-title":"Combin. Probab. Comput."},{"key":"9545_CR9","unstructured":"Coja-Oghlan, A., Krivelevich, M., Vilenchik, D.: Why almost all $$k$$ k -colorable graphs are easy to color. J. Theory Comput. Syst. 46, 523\u2013565 (2009)"},{"key":"9545_CR10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF01404753","volume":"66","author":"R Connelly","year":"1982","unstructured":"Connelly, R.: Rigidity and energy. Invent. Math. 66, 11\u201333 (1982)","journal-title":"Invent. Math."},{"key":"9545_CR11","doi-asserted-by":"crossref","unstructured":"Connelly, R.: Rigidity. In: Handbook of Convex Geometry, vol. A, pp. 223\u2013271. North-Holland, Amsterdam (1993)","DOI":"10.1016\/B978-0-444-89596-7.50012-2"},{"key":"9545_CR12","unstructured":"Connelly, R.: Stress and Stability, Chapt. II. Unfinished monograph (2001)"},{"key":"9545_CR13","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1137\/S0895480192229236","volume":"9","author":"R Connelly","year":"1996","unstructured":"Connelly, R., Whiteley, W.: Second-order rigidity and prestress stability for tensegrity frameworks. SIAM J. Discrete Math. 9, 453\u2013491 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9545_CR14","unstructured":"Crippen, G., Havel, T.: Distance geometry and molecular conformation. In: Chemometrics Series, vol. 15. Research Studies Press, Somerset (1988)"},{"key":"9545_CR15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0167-6377(97)00011-4","volume":"20","author":"E de-Klerk","year":"1997","unstructured":"de-Klerk, E., Roos, C., Terlaky, T.: Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper. Res. Lett. 20, 213\u2013221 (1997)","journal-title":"Oper. Res. Lett."},{"key":"9545_CR16","doi-asserted-by":"crossref","unstructured":"de-Klerk, E., Roos C., Terlaky, T.: Infeasible-start semidefinite programming algorithms via self-dual embeddings. In: Topics in Semidefinite and Interior-Point Methods, vol. 18, pp. 215\u2013236. AMS, Providence (1998)","DOI":"10.1090\/fic\/018\/15"},{"key":"9545_CR17","unstructured":"Doherty, L., Pister K., Ghaoui, L.E.: Convex position estimation in wireless sensor networks. In: Proceedings of INFOCOM, pp. 1655\u20131663 (2001)"},{"key":"9545_CR18","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1215\/S0012-7094-05-12926-X","volume":"129","author":"M Fedorchuk","year":"2005","unstructured":"Fedorchuk, M., Pak, I.: Rigidity and polynomial invariants of convex polytopes. Duke Math. J. 129, 371\u2013404 (2005)","journal-title":"Duke Math. J."},{"key":"9545_CR19","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539703431391","volume":"33","author":"U Feige","year":"2004","unstructured":"Feige, U., Langberg, M., Schechtman, G.: Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J. Comput. 33, 1338\u20131368 (2004)","journal-title":"SIAM J. Comput."},{"key":"9545_CR20","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.jctb.2007.10.007","volume":"98","author":"C Godsil","year":"2008","unstructured":"Godsil, C., Newman, M.: Eigenvalue bounds for independent sets. J. Combin. Theory Ser. B 98, 721\u2013734 (2008)","journal-title":"J. Combin. Theory Ser. B"},{"key":"9545_CR21","doi-asserted-by":"crossref","unstructured":"Goemans, M., Williamson, D.: 879-approximation algorithms for MAX CUT and MAX 2SAT. In: Proceedings of the 26th STOC, pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"key":"9545_CR22","unstructured":"Gortler, S.J., Thurston, D.P.: Characterizing the universal rigidity of generic frameworks. http:\/\/arxiv\/abs\/1001.0172"},{"key":"9545_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"9545_CR24","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/S0021-9800(69)80086-4","volume":"6","author":"F Harary","year":"1969","unstructured":"Harary, F., Hedetniemi, S.T., Robinson, R.W.: Uniquely colourable graphs. J. Combin. Theory 6, 264\u2013270 (1969)","journal-title":"J. Combin. Theory"},{"key":"9545_CR25","volume-title":"Multiple View Geometry in Computer Vision","author":"R Hartley","year":"2001","unstructured":"Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2001)"},{"key":"9545_CR26","doi-asserted-by":"crossref","first-page":"S37","DOI":"10.1002\/mrc.1242","volume":"41","author":"T Havel","year":"2003","unstructured":"Havel, T.: Metric matrix embedding in protein structure calculations. Magn. Reson. Chem. 41, S37\u2013S50 (2003)","journal-title":"Magn. Reson. Chem."},{"key":"9545_CR27","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"9545_CR28","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/0221008","volume":"21","author":"B Hendrickson","year":"1992","unstructured":"Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21, 65\u201384 (1992)","journal-title":"SIAM J. Comput."},{"key":"9545_CR29","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43, 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"key":"9545_CR30","volume-title":"Product Graphs","author":"W Imrich","year":"2000","unstructured":"Imrich, W., Klav\u017ear, S.: Product Graphs. Wiley, New York (2000)"},{"key":"9545_CR31","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D Karger","year":"1998","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45, 246\u2013265 (1998)","journal-title":"J. ACM"},{"key":"9545_CR32","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01894680","volume":"19","author":"L Lov\u00e1sz","year":"1968","unstructured":"Lov\u00e1sz, L.: On chromatic number of finite set-systems. Acta Math. Acad. Sci. Hung. 19, 59\u201367 (1968)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9545_CR33","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"9545_CR34","doi-asserted-by":"crossref","first-page":"721","DOI":"10.2307\/2371222","volume":"53","author":"K Menger","year":"1931","unstructured":"Menger, K.: New foundation of euclidean geometry. Am. J. Math. 53, 721\u2013745 (1931)","journal-title":"Am. J. Math."},{"key":"9545_CR35","doi-asserted-by":"crossref","unstructured":"Michel, X., Goemans, D.P.: Williamson:879-approximation algorithms for MAX CUT and MAX 2SAT. In: Proceedings of STOC, pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"key":"9545_CR36","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1090\/S0002-9947-1981-0610958-6","volume":"265","author":"B Roth","year":"1981","unstructured":"Roth, B., Whiteley, W.: Tensegrity frameworks. Trans. Am. Math. Soc. 265, 419\u2013446 (1981)","journal-title":"Trans. Am. Math. Soc."},{"key":"9545_CR37","unstructured":"Saxe, J.B.: Embeddability of weighted graphs in $$k$$ k -space is strongly NP-hard. In: Proceedings of 17th Allerton Conference on Communication, Control, and Computing, pp. 480\u2013489 (1979)"},{"key":"9545_CR38","unstructured":"So, A.: A semidefinite programming approach to the graph realization problem. Ph.D. Thesis, Stanford University, Stanford (2007)"},{"key":"9545_CR39","first-page":"1327","volume-title":"Handbook of Discrete and Computational Geometry","author":"W Whiteley","year":"2004","unstructured":"Whiteley, W.: Rigidity and scene analysis. In: Goodman, J., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn, pp. 1327\u20131354. SRC, Boca Raton (2004)","edition":"2"},{"key":"9545_CR40","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0012-365X(00)00217-X","volume":"229","author":"X Zhu","year":"2001","unstructured":"Zhu, X.: Circular chromatic number: a survey. Discrete Math. 229, 371\u2013410 (2001)","journal-title":"Discrete Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9545-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-013-9545-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9545-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T07:48:59Z","timestamp":1564040939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-013-9545-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,25]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["9545"],"URL":"https:\/\/doi.org\/10.1007\/s00454-013-9545-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,25]]}}}