{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:49:58Z","timestamp":1761709798064,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,7]]},"abstract":"Abstract<\/jats:title>A d<\/jats:italic>-dimensional framework is a pair (G<\/jats:italic>,\u00a0p<\/jats:italic>), where $$G=(V,E)$$<\/jats:tex-math>\n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a graph and p<\/jats:italic> is a map from V<\/jats:italic> to\u00a0$$\\mathbb {R}^d$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The length of an edge $$uv\\in E$$<\/jats:tex-math>\n \n u<\/mml:mi>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in (G<\/jats:italic>,\u00a0p<\/jats:italic>) is the distance between p<\/jats:italic>(u<\/jats:italic>) and p<\/jats:italic>(v<\/jats:italic>). The framework is said to be globally rigid in\u00a0$$\\mathbb {R}^d$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if every other d<\/jats:italic>-dimensional framework (G<\/jats:italic>,\u00a0q<\/jats:italic>), in which the corresponding edge lengths are the same, is congruent to (G<\/jats:italic>,\u00a0p<\/jats:italic>). In a recent paper Gortler, Theran, and Thurston proved that if every generic framework (G<\/jats:italic>,\u00a0p<\/jats:italic>) in\u00a0$$\\mathbb {R}^d$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is globally rigid for some graph G<\/jats:italic> on $$n\\ge d+2$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \u2265<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices (where $$d\\ge 2$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), then already the set of (unlabeled) edge lengths of a generic framework (G<\/jats:italic>,\u00a0p<\/jats:italic>), together with\u00a0n<\/jats:italic>, determine the framework up to congruence. In this paper we investigate the corresponding unlabeled reconstruction problem in the case when the above generic global rigidity property does not hold for the graph. We provide families of graphs G<\/jats:italic> for which the set of (unlabeled) edge lengths of any generic framework (G<\/jats:italic>,\u00a0p<\/jats:italic>) in d<\/jats:italic>-space, along with the number of vertices, uniquely determine the graph, up to isomorphism. We call these graphs weakly reconstructible. We also introduce the concept of strong reconstructibility; in this case the labeling of the edges is also determined by the set of edge lengths of any generic framework. For $$d=1,2$$<\/jats:tex-math>\n \n d<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> we give a partial characterization of weak reconstructibility as well as a complete characterization of strong reconstructibility of graphs. In particular, in the low-dimensional cases we describe the family of weakly reconstructible graphs that are rigid but not redundantly rigid.<\/jats:p>","DOI":"10.1007\/s00454-021-00275-7","type":"journal-article","created":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T21:02:40Z","timestamp":1614373360000},"page":"344-385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Graph Reconstruction from Unlabeled Edge Lengths"],"prefix":"10.1007","volume":"66","author":[{"given":"D\u00e1niel","family":"Garamv\u00f6lgyi","sequence":"first","affiliation":[]},{"given":"Tibor","family":"Jord\u00e1n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,26]]},"reference":[{"key":"275_CR1","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1090\/S0002-9947-1978-0511410-9","volume":"245","author":"L Asimow","year":"1978","unstructured":"Asimow, L., Roth, B.: The rigidity of graphs. Trans. Am. Math. Soc. 245, 279\u2013289 (1978)","journal-title":"Trans. Am. Math. Soc."},{"key":"275_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006)"},{"issue":"4","key":"275_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10288-016-0314-2","volume":"14","author":"SJL Billinge","year":"2016","unstructured":"Billinge, S.J.L., Duxbury, P.M., Gon\u00e7alves, D.S., Lavor, C., Mucherino, A.: Assigned and unassigned distance geometry: applications to biological molecules and nanostructures. 4OR 14(4), 337\u2013376 (2016)","journal-title":"4OR"},{"issue":"4","key":"275_CR4","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/S0196-8858(03)00101-5","volume":"32","author":"M Boutin","year":"2004","unstructured":"Boutin, M., Kemper, G.: On reconstructing $$n$$-point configurations from the distribution of distances or areas. Adv. Appl. Math. 32(4), 709\u2013735 (2004)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"275_CR5","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s00454-004-1124-4","volume":"33","author":"R Connelly","year":"2005","unstructured":"Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33(4), 549\u2013563 (2005)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"275_CR6","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00454-009-9220-0","volume":"43","author":"R Connelly","year":"2010","unstructured":"Connelly, R., Whiteley, W.J.: Global rigidity: the effect of coning. Discrete Comput. Geom. 43(4), 717\u2013735 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"275_CR7","unstructured":"Gkioulekas, I., Gortler, S.J., Theran, L., Zickler, T.: Linear symmetries of the unsquared measurement variety (2020). arXiv:2007.12649"},{"key":"275_CR8","doi-asserted-by":"crossref","unstructured":"Gluck, H.: Almost all simply connected closed surfaces are rigid. In: Geometric Topology (Park City 1974). Lecture Notes in Mathematics, vol. 438, pp. 225\u2013239. Springer, Berlin (1975)","DOI":"10.1007\/BFb0066118"},{"issue":"4","key":"275_CR9","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1353\/ajm.0.0132","volume":"132","author":"SJ Gortler","year":"2010","unstructured":"Gortler, S.J., Healy, A.D., Thurston, D.P.: Characterizing generic global rigidity. Am. J. Math. 132(4), 897\u2013939 (2010)","journal-title":"Am. J. Math."},{"key":"275_CR10","doi-asserted-by":"crossref","unstructured":"Gortler, S.J., Theran, L., Thurston, D.P.: Generic unlabeled global rigidity. Forum Math. Sigma 7, #\u00a0e21 (2019)","DOI":"10.1017\/fms.2019.16"},{"key":"275_CR11","doi-asserted-by":"crossref","unstructured":"Gortler, S.J., Thurston, D.P.: Generic global rigidity in complex and pseudo-Euclidean spaces. In: Rigidity and Symmetry. Fields Institute Communications, vol. 70, pp. 131\u2013154. Springer, New York (2014)","DOI":"10.1007\/978-1-4939-0781-6_8"},{"issue":"1","key":"275_CR12","doi-asserted-by":"publisher","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(1), 65\u201384 (1992)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"275_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2004.11.002","volume":"94","author":"B Jackson","year":"2005","unstructured":"Jackson, B., Jord\u00e1n, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory Ser. B 94(1), 1\u201329 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"275_CR14","doi-asserted-by":"crossref","unstructured":"Jackson, B., Jord\u00e1n, T.: Graph theoretic techniques in the analysis of uniquely localizable sensor networks. In: Localization Algorithms and Strategies for Wireless Sensor Networks, pp. 146\u2013173. IGI Global, Hershey (2009)","DOI":"10.4018\/978-1-60566-396-8.ch006"},{"issue":"3","key":"275_CR15","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00454-005-1225-8","volume":"35","author":"B Jackson","year":"2006","unstructured":"Jackson, B., Jord\u00e1n, T., Szabadka, Z.: Globally linked pairs of vertices in equivalent realizations of graphs. Discrete Comput. Geom. 35(3), 493\u2013512 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"275_CR16","doi-asserted-by":"crossref","unstructured":"Jord\u00e1n, T.: Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks. In: Discrete Geometric Analysis. MSJ Memoirs, vol. 34, pp. 33\u2013112. Math. Soc. Japan, Tokyo (2016)","DOI":"10.2969\/msjmemoirs\/03401C020"},{"issue":"2","key":"275_CR17","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.ejc.2012.09.001","volume":"34","author":"T Jord\u00e1n","year":"2013","unstructured":"Jord\u00e1n, T., Kaszanitzky, V.E.: Highly connected rigidity matroids have unique underlying graphs. Eur. J. Comb. 34(2), 240\u2013247 (2013)","journal-title":"Eur. J. Comb."},{"key":"275_CR18","unstructured":"Jord\u00e1n, T., Whiteley, W.: Global rigidity. In: Handbook of Discrete and Computational Geometry, 3rd ed. Discrete Mathematics and Its Applications, pp. 1661\u20131694. CRC Press, Boca Raton (2017)"},{"issue":"2","key":"275_CR19","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1137\/0603025","volume":"3","author":"MM Klawe","year":"1982","unstructured":"Klawe, M.M., Corneil, D.G., Proskurowski, A.: Isomorphism testing in hookup classes. SIAM J. Algebr. Discrete Methods 3(2), 260\u2013274 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"275_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/120875909","volume":"56","author":"L Liberti","year":"2014","unstructured":"Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3\u201369 (2014)","journal-title":"SIAM Rev."},{"issue":"1","key":"275_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0603009","volume":"3","author":"L Lov\u00e1sz","year":"1982","unstructured":"Lov\u00e1sz, L., Yemini, Y.: On generic rigidity in the plane. SIAM J. Algebr. Discrete Methods 3(1), 91\u201398 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"275_CR22","volume-title":"Topology","author":"JR Munkres","year":"2000","unstructured":"Munkres, J.R.: Topology. Prentice Hall, Upper Saddle River (2000)"},{"key":"275_CR23","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford Science Publications, Clarendon Press\u2013Oxford University Press, New York (1992)"},{"issue":"3","key":"275_CR24","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1080\/00029890.2020.1689781","volume":"127","author":"Z Rosen","year":"2020","unstructured":"Rosen, Z., Sidman, J., Theran, L.: Algebraic matroids in action. Am. Math. Mon. 127(3), 199\u2013216 (2020)","journal-title":"Am. Math. Mon."},{"key":"275_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38010-5","volume-title":"Basic Algebraic Geometry 1: Varieties in Projective Space","author":"IR Shafarevich","year":"2013","unstructured":"Shafarevich, I.R.: Basic Algebraic Geometry 1: Varieties in Projective Space. Springer, Heidelberg (2013)"},{"key":"275_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0021-9800(70)80005-9","volume":"8","author":"ME Watkins","year":"1970","unstructured":"Watkins, M.E.: Connectivity of transitive graphs. J. Comb. Theory 8, 23\u201329 (1970)","journal-title":"J. Comb. Theory"},{"issue":"8","key":"275_CR27","first-page":"53","volume":"1983","author":"W Whiteley","year":"1983","unstructured":"Whiteley, W.: Cones, infinity and $$1$$-story buildings. Struct. Topol. 1983(8), 53\u201370 (1983)","journal-title":"Struct. Topol."},{"key":"275_CR28","doi-asserted-by":"crossref","unstructured":"Whiteley, W.: Some matroids from discrete applied geometry. In: Matroid Theory (Seattle 1995). Contemporary Mathematics, vol. 197, pp. 171\u2013311. American Mathematical Society, Providence (1996)","DOI":"10.1090\/conm\/197\/02540"},{"issue":"1","key":"275_CR29","doi-asserted-by":"publisher","first-page":"245","DOI":"10.2307\/2371127","volume":"55","author":"H Whitney","year":"1933","unstructured":"Whitney, H.: $$2$$-Isomorphic graphs. Am. J. Math. 55(1), 245\u2013254 (1933)","journal-title":"Am. J. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00275-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00275-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00275-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T15:10:05Z","timestamp":1623251405000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00275-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,26]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["275"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00275-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2021,2,26]]},"assertion":[{"value":"5 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}