{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T08:11:12Z","timestamp":1773475872144,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2007,9]]},"DOI":"10.1007\/s00493-007-2183-y","type":"journal-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T01:20:29Z","timestamp":1211937629000},"page":"551-585","source":"Crossref","is-referenced-by-count":11,"title":["The intrinsic dimensionality of graphs"],"prefix":"10.1007","volume":"27","author":[{"given":"Robert","family":"Krauthgamer","sequence":"first","affiliation":[]},{"given":"James R.","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,29]]},"reference":[{"key":"2183_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"N. Alon and J. H. Spencer: The probabilistic method, Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000.","edition":"second edition"},{"issue":"4","key":"2183_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"P. Assouad: Plongements lipschitziens dans R n, Bull. Soc. Math. France 111(4) (1983), 429\u2013448.","journal-title":"Bull. Soc. Math. France"},{"key":"2183_CR3","doi-asserted-by":"crossref","unstructured":"Y. Bartal: Probabilistic approximation of metric spaces and its algorithmic applications, in 37th Annual Symposium on Foundations of Computer Science, pages 184\u2013193, IEEE, 1996.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"2183_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and U. S. R. Murty: Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976."},{"issue":"1","key":"2183_CR5","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"A. Brandst\u00e4dt, V. Chepoi and F. Dragan: Distance approximating trees for chordal and dually chordal graphs, J. Algorithms 30(1) (1999), 166\u2013184.","journal-title":"J. Algorithms"},{"issue":"6","key":"2183_CR6","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"V. Chepoi and F. Dragan: A note on distance approximating trees in graphs, European J. Combin. 21(6) (2000), 761\u2013766.","journal-title":"European J. Combin."},{"key":"2183_CR7","first-page":"151","volume-title":"Selected topics in graph theory","author":"F. R. K. Chung","year":"1988","unstructured":"F. R. K. Chung: Labelings of graphs, in Selected topics in graph theory, 3, pages 151\u2013168, Academic Press, San Diego, CA, 1988."},{"key":"2183_CR8","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1112\/S0025579300005222","volume":"12","author":"P. Erd\u0151s","year":"1965","unstructured":"P. Erd\u0151s, F. Harary and W. T. Tutte: On the dimension of a graph, Mathematika 12 (1965), 118\u2013122.","journal-title":"Mathematika"},{"issue":"3","key":"2183_CR9","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1006\/jcss.1999.1682","volume":"60","author":"U. Feige","year":"2000","unstructured":"U. Feige: Approximating the bandwidth via volume respecting embeddings, J. Comput. System Sci. 60(3) (2000), 510\u2013539.","journal-title":"J. Comput. System Sci."},{"key":"2183_CR10","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol and K. Talwar: An improved decomposition theorem for graphs excluding a fixed minor, in Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization, Springer Lecture Notes in Computer Science 2764, 36\u201346, 2003.","DOI":"10.1007\/978-3-540-45198-3_4"},{"key":"2183_CR11","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer and J. R. Lee: Bounded geometries, fractals, and low-distortion embeddings; in Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 2003.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"2183_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on analysis on metric spaces","author":"J. Heinonen","year":"2001","unstructured":"J. Heinonen: Lectures on analysis on metric spaces, Universitext, Springer-Verlag, New York, 2001."},{"key":"2183_CR13","doi-asserted-by":"crossref","unstructured":"P. Indyk: Algorithmic applications of low-distortion geometric embeddings, in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 10\u201333, October 2001.","DOI":"10.1109\/SFCS.2001.959878"},{"key":"2183_CR14","doi-asserted-by":"crossref","unstructured":"P. Klein, S. A. Plotkin and S. Rao: Excluded minors, network decomposition, and multicommodity flow; in 25th Annual ACM Symposium on Theory of Computing, pages 682\u2013690, May 1993.","DOI":"10.1145\/167088.167261"},{"key":"2183_CR15","unstructured":"N. Linial: Variation on a theme of Levin, in Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications (J. Matou\u0161ek, ed.), Haifa, March 2002."},{"issue":"2","key":"2183_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"N. Linial, E. London and Y. Rabinovich: The geometry of graphs and some of its algorithmic applications, Combinatorica 15(2) (1995), 215\u2013245.","journal-title":"Combinatorica"},{"issue":"4","key":"2183_CR17","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N. Linial","year":"1993","unstructured":"N. Linial and M. Saks: Low diameter graph decompositions, Combinatorica 13(4) (1993), 441\u2013454.","journal-title":"Combinatorica"},{"key":"2183_CR18","unstructured":"L. Lov\u00e1sz and K. Vesztergombi: Geometric representations of graphs, in Paul Erd\u0151s, Proc. Conf., Budapest, 1999."},{"key":"2183_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on discrete geometry, Vol. 212 of Graduate Texts in Mathematics","author":"J. Matou\u0161ek","year":"2002","unstructured":"J. Matou\u0161ek: Lectures on discrete geometry, Vol. 212 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2002."},{"key":"2183_CR20","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"2183_CR21","doi-asserted-by":"crossref","unstructured":"S. Rao: Small distortion and volume preserving embeddings for planar and Euclidean metrics, in Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300\u2013306, ACM, 1999.","DOI":"10.1145\/304893.304983"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-007-2183-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-007-2183-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-007-2183-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:45Z","timestamp":1559079165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-007-2183-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["2183"],"URL":"https:\/\/doi.org\/10.1007\/s00493-007-2183-y","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}