{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T11:13:35Z","timestamp":1762254815370,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T00:00:00Z","timestamp":1712534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T00:00:00Z","timestamp":1712534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009934","name":"E\u00f6tv\u00f6s Lor\u00e1nd University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009934","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,8]]},"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 $${\\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 $$xy\\in E$$<\/jats:tex-math>\n \n x<\/mml:mi>\n y<\/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>(x<\/jats:italic>) and p<\/jats:italic>(y<\/jats:italic>). A vertex pair $$\\{u,v\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic> is said to be globally linked in (G<\/jats:italic>,\u00a0p<\/jats:italic>) if the distance between p<\/jats:italic>(u<\/jats:italic>) and p<\/jats:italic>(v<\/jats:italic>) is equal to the distance between q<\/jats:italic>(u<\/jats:italic>) and q<\/jats:italic>(v<\/jats:italic>) for every d<\/jats:italic>-dimensional framework (G<\/jats:italic>,\u00a0q<\/jats:italic>) in which the corresponding edge lengths are the same as in (G<\/jats:italic>,\u00a0p<\/jats:italic>). We call (G<\/jats:italic>,\u00a0p<\/jats:italic>) globally rigid in $${\\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> when each vertex pair of G<\/jats:italic> is globally linked in (G<\/jats:italic>,\u00a0p<\/jats:italic>). A pair $$\\{u,v\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of vertices of G<\/jats:italic> is said to be weakly globally linked in G<\/jats:italic> in $${\\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 there exists a generic framework (G<\/jats:italic>,\u00a0p<\/jats:italic>) in which $$\\{u,v\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is globally linked. In this paper we first give a sufficient condition for the weak global linkedness of a vertex pair of a $$(d+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-connected graph G<\/jats:italic> in $${\\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> and then show that for $$d=2$$<\/jats:tex-math>\n \n d<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> it is also necessary. We use this result to obtain a complete characterization of weakly globally linked pairs in graphs in $${\\mathbb {R}}^2$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which gives rise to an algorithm for testing weak global linkedness in the plane in $$O(|V|^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n |<\/mml:mo>\n V<\/mml:mi>\n \n |<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Our methods lead to a new short proof for the characterization of globally rigid graphs in $${\\mathbb {R}}^2$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and further results on weakly globally linked pairs and globally rigid graphs in the plane and in higher dimensions.<\/jats:p>","DOI":"10.1007\/s00493-024-00094-3","type":"journal-article","created":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T07:01:51Z","timestamp":1712559711000},"page":"817-838","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Globally Linked Pairs of Vertices in Generic Frameworks"],"prefix":"10.1007","volume":"44","author":[{"given":"Tibor","family":"Jord\u00e1n","sequence":"first","affiliation":[]},{"given":"Soma","family":"Vill\u00e1nyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,8]]},"reference":[{"key":"94_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":"94_CR2","doi-asserted-by":"crossref","unstructured":"Berg, A.R., Jord\u00e1n, T.: Algorithms for graph rigidity and scene analysis. In: Proceedings of 11th Annual European Symposium on Algorithms (ESA) 2003. Springer LNCS 2832, pp. 78\u201389 (2003)","DOI":"10.1007\/978-3-540-39658-1_10"},{"key":"94_CR3","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. Discret. Comput. Geom. 33, 549\u2013563 (2005)","journal-title":"Discret. Comput. Geom."},{"key":"94_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1134\/S008154381108013X","volume":"275","author":"R Connelly","year":"2011","unstructured":"Connelly, R.: Combining globally rigid frameworks. Proc. Steklov Inst. Math. 275, 191\u2013198 (2011)","journal-title":"Proc. Steklov Inst. Math."},{"key":"94_CR5","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.: Global rigidity: the effect of coning. Discret. Comput Geom. 43, 717\u2013735 (2010)","journal-title":"Discret. Comput Geom."},{"key":"94_CR6","unstructured":"Garamv\u00f6lgyi, D.: Stress-linked pairs of vertices and the generic stress matroid (2023). arXiv:2308.16851"},{"issue":"1","key":"94_CR7","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/18M1220662","volume":"34","author":"D Garamv\u00f6lgyi","year":"2020","unstructured":"Garamv\u00f6lgyi, D., Jord\u00e1n, T.: Global rigidity of unit ball graphs. SIAM J. Discret. Math. 34(1), 212\u2013229 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"94_CR8","unstructured":"Garamv\u00f6lgyi, D., Jord\u00e1n, T.: Globally linked pairs in braced maximal outerplanar graphs. In: Proceedings of CCCG 2022, Toronto (2022), pp. 162\u2013168"},{"key":"94_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2022.103626","volume":"108","author":"D Garamv\u00f6lgyi","year":"2023","unstructured":"Garamv\u00f6lgyi, D., Jord\u00e1n, T.: Minimally globally rigid graphs. Eur. J. Comb. 108, 103626 (2023)","journal-title":"Eur. J. Comb."},{"key":"94_CR10","doi-asserted-by":"crossref","unstructured":"Garamv\u00f6lgyi, D., Jord\u00e1n, T.: Partial reflections and globally linked pairs in rigid graphs (2023). arXiv:2305.03412","DOI":"10.1137\/23M157065X"},{"key":"94_CR11","doi-asserted-by":"crossref","unstructured":"Gluck, H.: Almost all simply connected closed surfaces are rigid. In: Geometric Topology. Proceedings of Conference, Park City, Utah, 1974), pp. 225\u2013239. Lecture Notes in Mathematics, vol. 438, Springer, Berlin (1975)","DOI":"10.1007\/BFb0066118"},{"issue":"4","key":"94_CR12","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1353\/ajm.0.0132","volume":"132","author":"S Gortler","year":"2010","unstructured":"Gortler, S., Healy, A., Thurston, D.: Characterizing generic global rigidity. Am. J. Math. 132(4), 897\u2013939 (2010)","journal-title":"Am. J. Math."},{"issue":"1","key":"94_CR13","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."},{"key":"94_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2, 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"94_CR15","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\u201329 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"94_CR16","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. Discret. Comput. Geom. 35, 493\u2013512 (2006)","journal-title":"Discret. Comput. Geom."},{"key":"94_CR17","doi-asserted-by":"crossref","unstructured":"Jackson, B., Jord\u00e1n, T., Szabadka, Z.: Globally linked pairs of vertices in rigid frameworks. In: Rigidity and Symmetry, Fields Institute Communications, vol. 70, pp. 177\u2013203 (2014)","DOI":"10.1007\/978-1-4939-0781-6_10"},{"key":"94_CR18","first-page":"33","volume":"34","author":"T Jord\u00e1n","year":"2016","unstructured":"Jord\u00e1n, T.: Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks. Discret. Geom. Anal. MSJ Mem. 34, 33\u2013112 (2016)","journal-title":"Discret. Geom. Anal. MSJ Mem."},{"key":"94_CR19","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.jctb.2018.11.003","volume":"136","author":"T Jord\u00e1n","year":"2019","unstructured":"Jord\u00e1n, T., Tanigawa, S.: Global rigidity of triangulations with braces. J. Comb. Theory Ser. B. 136, 249\u2013288 (2019)","journal-title":"J. Comb. Theory Ser. B."},{"key":"94_CR20","unstructured":"Jord\u00e1n, T., Vill\u00e1nyi, S.: Globally linked pairs and cheapest globally rigid supergraphs (2024). arXiv:2401.09568"},{"key":"94_CR21","first-page":"1661","volume-title":"Handbook of Discrete and Computational Geometry","author":"T Jord\u00e1n","year":"2018","unstructured":"Jord\u00e1n, T., Whiteley, W.: Global rigidity. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn., pp. 1661\u20131694. CRC Press, Boca Raton (2018)","edition":"3"},{"key":"94_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.jctb.2015.11.003","volume":"117","author":"T Jord\u00e1n","year":"2016","unstructured":"Jord\u00e1n, T., Kir\u00e1ly, C., Tanigawa, S.: Generic global rigidity of body-hinge frameworks. J. Comb. Theory Ser. B 117, 59\u201376 (2016)","journal-title":"J. Comb. Theory Ser. B"},{"key":"94_CR23","volume-title":"Fast Algorithms for Sparsity Matroids and the Global Rigidity Augmentation Problem","author":"C Kir\u00e1ly","year":"2022","unstructured":"Kir\u00e1ly, C., Mih\u00e1lyk\u00f3, A.: Fast Algorithms for Sparsity Matroids and the Global Rigidity Augmentation Problem. Egerv\u00e1ry Research Group, Budapest (2022)"},{"key":"94_CR24","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G Laman","year":"1970","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331\u2013340 (1970)","journal-title":"J. Eng. Math."},{"key":"94_CR25","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Graphs and geometry. In: Colloquium Publications, vol. 69. American Mathematical Society, Providence (2019)","DOI":"10.1090\/coll\/065"},{"key":"94_CR26","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. The Clarendon Press, New York (1992)"},{"issue":"1","key":"94_CR27","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/zamm.19270070107","volume":"7","author":"H Pollaczek-Geiringer","year":"1927","unstructured":"Pollaczek-Geiringer, H.: \u00dcber die gliederung ebener fachwerke. Z. Angew. Math. Mech. 7(1), 58\u201372 (1927)","journal-title":"Z. Angew. Math. Mech."},{"key":"94_CR28","unstructured":"Saxe, J.B.: Embeddability of Weighted Graphs in $$k$$-Space is Strongly NP-Hard, Technical Report, Computer Science Department, Carnegie-Mellon University, Pittsburgh (1979)"},{"key":"94_CR29","volume-title":"Handbook of Discrete and Computational Geometry","author":"B Schulze","year":"2018","unstructured":"Schulze, B., Whiteley, W.: Rigidity and scene analysis. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press, Boca Raton (2018)","edition":"3"},{"key":"94_CR30","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.jctb.2015.01.003","volume":"113","author":"S Tanigawa","year":"2015","unstructured":"Tanigawa, S.: Sufficient conditions for the global rigidity of graphs. J. Comb. Theory Ser. B 113, 123\u2013140 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"key":"94_CR31","unstructured":"Vill\u00e1nyi, S.: Every $$d(d+1)$$-connected graph is globally rigid in $${\\mathbb{R}}^d$$ (2023). arXiv:2312.02028"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00094-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00094-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00094-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T17:05:21Z","timestamp":1721840721000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00094-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,8]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["94"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00094-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2024,4,8]]},"assertion":[{"value":"7 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}