{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T06:43:36Z","timestamp":1776581016944,"version":"3.51.2"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s00454-021-00285-5","type":"journal-article","created":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T14:02:57Z","timestamp":1621951377000},"page":"301-343","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Unavoidable Minors for Graphs with Large $$\\ell _p$$-Dimension"],"prefix":"10.1007","volume":"66","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[]},{"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7157-6694","authenticated-orcid":false,"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[]},{"given":"Carole","family":"Muller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,25]]},"reference":[{"issue":"6","key":"285_CR1","doi-asserted-by":"publisher","first-page":"3026","DOI":"10.1016\/j.aim.2011.08.003","volume":"228","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026\u20133126 (2011)","journal-title":"Adv. Math."},{"issue":"4","key":"285_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","volume":"11","author":"K Ball","year":"1990","unstructured":"Ball, K.: Isometric embedding in $$l_p$$-spaces. Eur. J. Comb. 11(4), 305\u2013311 (1990)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"285_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00454-006-1285-4","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M.: Realizability of graphs in three dimensions. Discrete Comput. Geom. 37(2), 139\u2013162 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"285_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00454-006-1284-5","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M., Connelly, R.: Realizability of graphs. Discrete Comput. Geom. 37(2), 125\u2013137 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"285_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Isr. J. Math."},{"issue":"5","key":"285_CR6","doi-asserted-by":"publisher","first-page":"#40","DOI":"10.1145\/2820609","volume":"63","author":"Ch Chekuri","year":"2016","unstructured":"Chekuri, Ch., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM 63(5), #40 (2016)","journal-title":"J. ACM"},{"key":"285_CR7","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Tan, Z.: Towards tight(er) bounds for the excluded grid theorem. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms (San Diego 2019), pp. 1445\u20131464. SIAM, Philadelphia (2019)","DOI":"10.1137\/1.9781611975482.88"},{"key":"285_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics. Algorithms and Combinatorics","author":"MM Deza","year":"1997","unstructured":"Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)"},{"issue":"4","key":"285_CR9","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"285_CR10","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2017)"},{"key":"285_CR11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jctb.2014.02.011","volume":"108","author":"M E.-Nagy","year":"2014","unstructured":"E.-Nagy, M., Laurent, M., Varvitsiotis, A.: Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. J. Comb. Theory Ser. B 108, 40\u201380 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"285_CR12","first-page":"463","volume":"2","author":"P Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"1","key":"285_CR13","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1137\/16M1064775","volume":"31","author":"S Fiorini","year":"2017","unstructured":"Fiorini, S., Huynh, T., Joret, G., Varvitsiotis, A.: The excluded minors for isometric realizability in the plane. SIAM J. Discrete Math. 31(1), 438\u2013453 (2017)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"285_CR14","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1137\/120883736","volume":"28","author":"G Joret","year":"2014","unstructured":"Joret, G., Paul, Ch., Sau, I., Saurabh, S., Thomass\u00e9, S.: Hitting and harvesting pumpkins. SIAM J. Discrete Math. 28(3), 1363\u20131390 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"285_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.laa.2020.08.004","volume":"607","author":"D Kitson","year":"2020","unstructured":"Kitson, D., Nixon, A., Schulze, B.: Rigidity of symmetric frameworks in normed spaces. Linear Algebra Appl. 607, 231\u2013285 (2020)","journal-title":"Linear Algebra Appl."},{"issue":"1\u20132","key":"285_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10107-013-0648-x","volume":"145","author":"M Laurent","year":"2014","unstructured":"Laurent, M., Varvitsiotis, A.: A new graph parameter related to bounded rank positive semidefinite matrix completions. Math. Program. 145(1\u20132), 291\u2013325 (2014)","journal-title":"Math. Program."},{"key":"285_CR17","unstructured":"Muller, C.: Excluded Minors for Isometric Embeddings of Graphs in $$\\ell _\\infty ^k$$-Spaces. MSc thesis, Universit\u00e9 Libre de Bruxelles (2017)"},{"issue":"1","key":"285_CR18","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"285_CR19","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"285_CR20","unstructured":"Saxe, J.B.: Embeddability of weighted graphs in $$k$$-space is strongly NP-hard. In: 17th Allerton Conference in Communications, Control and Computing (Monticello 1979), pp. 480\u2013489 (1979)"},{"key":"285_CR21","doi-asserted-by":"crossref","unstructured":"Schulze, B.: Combinatorial rigidity of symmetric and periodic frameworks. In: Handbook of Geometric Constraint Systems Principles. Discrete Math. Appl. (Boca Raton), pp. 543\u2013565. CRC Press, Boca Raton (2019)","DOI":"10.1201\/9781315121116-25"},{"key":"285_CR22","doi-asserted-by":"crossref","unstructured":"Sitharam, M., Willoughby, J.: On flattenability of graphs. Automated Deduction in Geometry (Coimbra 2014). Lecture Notes in Comput. Sci., vol. 9201. Lecture Notes in Artificial Intelligence, pp. 129\u2013148. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-21362-0_9"},{"issue":"2","key":"285_CR23","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0097-3165(86)90089-0","volume":"42","author":"HS Witsenhausen","year":"1986","unstructured":"Witsenhausen, H.S.: Minimum dimension embedding of finite metric spaces. J. Comb. Theory Ser. A 42(2), 184\u2013199 (1986)","journal-title":"J. Comb. Theory Ser. A"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00285-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00285-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00285-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T15:10:27Z","timestamp":1623251427000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00285-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,25]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["285"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00285-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,25]]},"assertion":[{"value":"26 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}