{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T02:34:26Z","timestamp":1778898866396,"version":"3.51.4"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T00:00:00Z","timestamp":1620864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T00:00:00Z","timestamp":1620864000000},"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","award":["K 135421"],"award-info":[{"award-number":["K 135421"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["2020-4.1.1.-TKP2020"],"award-info":[{"award-number":["2020-4.1.1.-TKP2020"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]},{"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":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph<jats:italic>G<\/jats:italic>is said to be<jats:italic>k<\/jats:italic>-vertex rigid in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mi>d<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>if<jats:inline-formula><jats:alternatives><jats:tex-math>$$G-X$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>G<\/mml:mi><mml:mo>-<\/mml:mo><mml:mi>X<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is rigid in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mi>d<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for all subsets<jats:italic>X<\/jats:italic>of the vertex set of<jats:italic>G<\/jats:italic>with cardinality less than<jats:italic>k<\/jats:italic>. We determine the smallest number of edges in a<jats:italic>k<\/jats:italic>-vertex rigid graph on<jats:italic>n<\/jats:italic>vertices in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mn>2<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for all<jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>k<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also consider<jats:italic>k<\/jats:italic>-edge-rigid graphs, defined by removing edges, as well as<jats:italic>k<\/jats:italic>-vertex globally rigid and<jats:italic>k<\/jats:italic>-edge globally rigid graphs in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mi>d<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For<jats:inline-formula><jats:alternatives><jats:tex-math>$$d=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>d<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>we determine the corresponding tight bounds for each of these versions, for all<jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>k<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our results complete the solutions of these extremal problems in the plane. The result on<jats:italic>k<\/jats:italic>-vertex rigidity verifies a conjecture of Kaszanitzky and Kir\u00e1ly (Graphs Combin, 32:225\u2013240, 2016). We also determine the degree of vertex redundancy of powers of cycles, with respect to rigidity in the plane, answering a question of Yu and Anderson (Int J Robust Nonlinear Control, 19(13):1427\u20131446, 2009).<\/jats:p>","DOI":"10.1007\/s00373-021-02327-4","type":"journal-article","created":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T03:41:16Z","timestamp":1620877276000},"page":"1415-1431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Minimum Size Highly Redundantly Rigid Graphs in the Plane"],"prefix":"10.1007","volume":"37","author":[{"given":"Tibor","family":"Jord\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,13]]},"reference":[{"key":"2327_CR1","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, 549\u2013563 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"2327_CR2","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, 65\u201384 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2327_CR3","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0805040","volume":"5","author":"B Hendrickson","year":"1995","unstructured":"Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5(4), 835\u2013857 (1995)","journal-title":"SIAM J. Optim."},{"key":"2327_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2004.11.002","volume":"9","author":"B Jackson","year":"2005","unstructured":"Jackson, B., Jord\u00e1n, T.: Connected rigidity matroids and unique realizations of graphs. J. Combin. Theory, Ser. B 9, 1\u201329 (2005)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"2327_CR5","doi-asserted-by":"publisher","first-page":"146","DOI":"10.4018\/978-1-60566-396-8.ch006","volume-title":"Localization Algorithms and Strategies for Wireless Sensor Networks","author":"B Jackson","year":"2009","unstructured":"Jackson, B., Jord\u00e1n, T.: Graph theoretic techniques in the analysis of uniquely localizable sensor networks. In: Mao, G., Fidan, B. (eds.) Localization Algorithms and Strategies for Wireless Sensor Networks, pp. 146\u2013173. IGI Global, Hershey (2009)"},{"key":"2327_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.2969\/msjmemoirs\/03401C020","volume":"34","author":"T Jord\u00e1n","year":"2016","unstructured":"Jord\u00e1n, T.: Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks. Discrete Geomet. Anal. MSJ Mem. 34, 33\u2013112 (2016)","journal-title":"Discrete Geomet. Anal. MSJ Mem."},{"key":"2327_CR7","doi-asserted-by":"crossref","unstructured":"Jord\u00e1n, T., Poston, C., Roach, R.: Extremal families of redundantly rigid graphs in three dimensions, manuscript, Egerv\u00e1ry Research Group, Budapest, Technical Report TR-2020-22","DOI":"10.1016\/j.dam.2022.03.006"},{"key":"2327_CR8","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 Roton (2018)","edition":"3"},{"key":"2327_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s00373-015-1560-3","volume":"32","author":"VE Kaszanitzky","year":"2016","unstructured":"Kaszanitzky, V.E., Kir\u00e1ly, C.S.: On minimally highly vertex-redundantly rigid graphs. Graphs Combin. 32, 225\u2013240 (2016)","journal-title":"Graphs Combin."},{"key":"2327_CR10","unstructured":"Kohta, R., Yamakawa, M., Katoh, N., Araki, Y., Ohsaki, M.: A design method for optimal truss structures with certain redundancy based on combinatorial rigidity theory. In: 10th World Congress on Structural and Multidisciplinary Optimization: Orlando. Florida, USA (May 2013)"},{"key":"2327_CR11","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1002\/rnc.3167","volume":"25","author":"SA Motevallian","year":"2015","unstructured":"Motevallian, S.A., Yu, C., Anderson, B.D.O.: On the robustness to multiple agent losses in 2D and 3D formations. Int. J. Robust Nonlinear Control 25, 1654\u20131687 (2015)","journal-title":"Int. J. Robust Nonlinear Control"},{"key":"2327_CR12","first-page":"1593","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., pp. 1593\u20131632. CRC Press, Boca Roton (2018)","edition":"3"},{"key":"2327_CR13","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1137\/0402050","volume":"8","author":"B Servatius","year":"1989","unstructured":"Servatius, B.: Birigidity in the plane. SIAM J. Discrete Math. 8, 582\u2013589 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"15","key":"2327_CR14","doi-asserted-by":"publisher","first-page":"1673","DOI":"10.1002\/rnc.1400","volume":"19","author":"TH Summers","year":"2009","unstructured":"Summers, T.H., Yu, C., Anderson, B.D.O.: Addressing agent loss in vehicle formations and sensor networks. Int. J. Robust Nonlinear Control 19(15), 1673\u20131696 (2009)","journal-title":"Int. J. Robust Nonlinear Control"},{"key":"2327_CR15","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. Combin. Theory Ser. B 113, 123\u2013140 (2015)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"13","key":"2327_CR16","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1002\/rnc.1386","volume":"19","author":"C Yu","year":"2009","unstructured":"Yu, C., Anderson, B.D.O.: Development of redundant rigidity theory for formation control. Int. J. Robust Nonlinear Control 19(13), 1427\u20131446 (2009)","journal-title":"Int. J. Robust Nonlinear Control"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02327-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-021-02327-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02327-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T06:04:42Z","timestamp":1672121082000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-021-02327-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,13]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["2327"],"URL":"https:\/\/doi.org\/10.1007\/s00373-021-02327-4","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,13]]},"assertion":[{"value":"11 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}]}}