{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T19:26:19Z","timestamp":1778700379417,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642321467","type":"print"},{"value":"9783642321474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32147-4_32","type":"book-chapter","created":{"date-parts":[[2012,7,5]],"date-time":"2012-07-05T11:54:50Z","timestamp":1341489290000},"page":"356-367","source":"Crossref","is-referenced-by-count":6,"title":["The Gram Dimension of a Graph"],"prefix":"10.1007","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Varvitsiotis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","volume":"8","author":"S. Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Corneil, D.G.: Forbidden minors characterization of partial 3-trees. Disc. Math.\u00a08(1), 1\u201319 (1990)","journal-title":"Disc. Math."},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/11538462_2","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Avidor","year":"2005","unstructured":"Avidor, A., Zwick, U.: Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX\u00a0CUT. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 14\u201325. Springer, Heidelberg (2005)"},{"issue":"3","key":"32_CR3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"Barahona, F.: The max-cut problem on graphs not contractible to K 5. Operations Research Letters\u00a02(3), 107\u2013111 (1983)","journal-title":"Operations Research Letters"},{"issue":"1","key":"32_CR4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s004540010074","volume":"25","author":"A. Barvinok","year":"2001","unstructured":"Barvinok, A.: A remark on the rank of positive semidefinite matrices subject to affine constraints. Disc. Comp. Geom.\u00a025(1), 23\u201331 (2001)","journal-title":"Disc. Comp. Geom."},{"key":"32_CR5","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. Disc. Comput. Geom.\u00a037, 139\u2013162 (2007)","journal-title":"Disc. Comput. Geom."},{"key":"32_CR6","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. Disc. Comput. Geom.\u00a037, 125\u2013137 (2007)","journal-title":"Disc. Comput. Geom."},{"issue":"6","key":"32_CR7","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"E.J. Candes","year":"2009","unstructured":"Candes, E.J., Recht, B.: Exact matrix completion via convex optimization. Foundations of Computational Mathematics\u00a09(6), 717\u2013772 (2009)","journal-title":"Foundations of Computational Mathematics"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Springer (1997)","DOI":"10.1007\/978-3-642-04295-9"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R.J. Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. Journal of Mathematical Analysis and Applications\u00a010(2), 303\u2013313 (1965)","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"E.-Nagy, M., Laurent, M., Varvitsiotis, A.: Complexity of the positive semidefinite matrix completion problem with a rank constraint (preprint, 2012)","DOI":"10.1007\/978-3-319-00200-2_7"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R. Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra and its Applications\u00a058, 109\u2013124 (1984)","journal-title":"Linear Algebra and its Applications"},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1002\/jgt.20502","volume":"66","author":"F. G\u00f6ring","year":"2011","unstructured":"G\u00f6ring, F., Helmberg, C., Wappler, M.: The rotational dimension of a graph. J. Graph Theory\u00a066(4), 283\u2013302 (2011)","journal-title":"J. Graph Theory"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"2560","DOI":"10.1016\/j.laa.2007.12.004","volume":"428","author":"L. Hogben","year":"2008","unstructured":"Hogben, L.: Orthogonal representations, minimum rank, and graph complements. Linear Algebra and its Applications\u00a0428, 2560\u20132568 (2008)","journal-title":"Linear Algebra and its Applications"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Matrix completion problems. In: Floudas, C.A., Pardalos, P.M. (eds.) The Encyclopedia of Optimization, vol.\u00a0III, pp. 221\u2013229. Kluwer (2001)","DOI":"10.1007\/0-306-48332-7_271"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Laurent, M., Varvitsiotis, A.: A new graph parameter related to bounded rank positive semidefinite matrix completions (preprint, 2012)","DOI":"10.1007\/s10107-013-0648-x"},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Th.\u00a0IT-25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Th."},{"key":"32_CR17","unstructured":"Lov\u00e1sz, L.: Semidefinite programs and combinatorial optimization. Lecture Notes (1995), http:\/\/www.cs.elte.hu\/~lovasz\/semidef.ps"},{"key":"32_CR18","unstructured":"Lov\u00e1sz, L.: Geometric representations of graphs. Lecture Notes (2001), http:\/\/www.cs.elte.hu\/~lovasz\/geomrep.pdf"},{"issue":"3","key":"32_CR19","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01261326","volume":"16","author":"R. Peeters","year":"1996","unstructured":"Peeters, R.: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica\u00a016(3), 417\u2013431 (1996)","journal-title":"Combinatorica"},{"issue":"3","key":"32_CR20","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B. Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review\u00a052(3), 471\u2013501 (2010)","journal-title":"SIAM Review"},{"issue":"2","key":"32_CR21","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. Wagners conjecture. J. Combin. Theory Ser. B\u00a092(2), 325\u2013357 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"32_CR22","unstructured":"Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proc. 17th Allerton Conf. Comm. Control Comp., pp. 480\u2013489 (1979)"},{"key":"32_CR23","unstructured":"Man-Cho So, A.: A semidefinite programming approach to the graph realization problem. PhD thesis, Stanford (2007)"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Man-Cho So, A., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 766\u2013775 (2006)","DOI":"10.1145\/1109557.1109641"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32147-4_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T07:20:05Z","timestamp":1743664805000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32147-4_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642321467","9783642321474"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32147-4_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}