{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:06:53Z","timestamp":1775581613716,"version":"3.50.1"},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"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":[[1995,6]]},"DOI":"10.1007\/bf01200757","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:13:34Z","timestamp":1108728814000},"page":"215-245","source":"Crossref","is-referenced-by-count":520,"title":["The geometry of graphs and some of its algorithmic applications"],"prefix":"10.1007","volume":"15","author":[{"given":"Nathan","family":"Linial","sequence":"first","affiliation":[]},{"given":"Eran","family":"London","sequence":"additional","affiliation":[]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF02187724","volume":"4","author":"N. Alon","year":"1989","unstructured":"N. Alon, M. Katchalski, andW. R. Pulleyblank: Cutting disjoint disks by straight lines,Discrete and Computational Geometry 4 (1989), 239?243.","journal-title":"Discrete and Computational Geometry"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\ufffdfer","year":"1993","unstructured":"I. Alth\ufffdfer, G. Das, D. Dobkin, D. Joseph, andJ. Soares: On sparse spanners of weighted graphs,Discrete and Computational Geometry 9 (1993), 81?100.","journal-title":"Discrete and Computational Geometry"},{"issue":"123","key":"CR3","first-page":"445","volume":"81","author":"E. M. Andreev","year":"1970","unstructured":"E. M. Andreev: Convex polyhedra in Loba?evski\ufffd spaces,Mat. Sb. (N.S.) 81 (123) (1970), 445?478. English translation:Math. USSR Sb. 10 (1970), 413?440.","journal-title":"Mat. Sb. (N.S.)"},{"issue":"125","key":"CR4","first-page":"256","volume":"83","author":"E. M. Andreev","year":"1970","unstructured":"E. M. Andreev: Convex polyhedra of finite volume in Loba?evski\ufffd space,Mat. Sb. (N.S.) 83 (125) (1970), 256?260. English translation:Math. USSR Sb. 12 (1970), 255?259.","journal-title":"Mat. Sb. (N.S.)"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF02764804","volume":"79","author":"J. Arias-de-Reyna","year":"1992","unstructured":"J. Arias-de-Reyna, andL. Rodr\ufffdgues-Piazza: Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces,Israel J. Math. 79 (1992), 103?111.","journal-title":"Israel J. Math."},{"key":"CR6","unstructured":"Y. Aumann, andY. Rabani: AnO(logk) approximate min-cut max-flow theorem and approximation algorithm, preprint, 1994."},{"key":"CR7","first-page":"503","volume":"31","author":"B. Awerbuch","year":"1990","unstructured":"B. Awerbuch, andD. Peleg: Sparse partitions,FOCS 31 (1990), 503?513.","journal-title":"FOCS"},{"key":"CR8","series-title":"Preliminary Version","volume-title":"Linear Algebra Methods in Combinatorics","author":"L. Babai","year":"1992","unstructured":"L. Babai, andD. Frankl:Linear Algebra Methods in Combinatorics, Preliminary Version 2, Department of Computer Science, The University of Chicago, Chicago, 1992."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","volume":"11","author":"K. Ball","year":"1990","unstructured":"K. Ball: Isometric embedding inl p -spaces,Europ. J. Combinatorics 11 (1990), 305?311.","journal-title":"Europ. J. Combinatorics"},{"key":"CR10","first-page":"373","volume":"2","author":"B. Berger","year":"1991","unstructured":"B. Berger: The fourth moment method,SODA 2 (1991), 373?383.","journal-title":"SODA"},{"key":"CR11","volume-title":"Theory and Applications of Distance Geometry","author":"L. M. Blumenthal","year":"1970","unstructured":"L. M. Blumenthal:Theory and Applications of Distance Geometry, Chelsea, New York, 1970."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"J. Bourgain: On Lipschitz embedding of finite metric spaces in Hilbert space,Israel J. Math. 52 (1985), 46?52.","journal-title":"Israel J. Math."},{"key":"CR13","volume-title":"Through the Looking-Glass and what Alice Found There","author":"L. Carroll","year":"1947","unstructured":"L. Carroll:Through the Looking-Glass and what Alice Found There, Chapter 6, Pan Books, London, 1947."},{"key":"CR14","first-page":"17","volume-title":"Paths, Flows, and VLSI-Layout","author":"F. R. K. Chung","year":"1990","unstructured":"F. R. K. Chung: Separator theorems and their applications, in:Paths, Flows, and VLSI-Layout, (B. Korte, L. Lov\ufffdsz, H. J. Pr\ufffdmel, and A. Schrijver eds.) Springer, Berlin-New York, 1990, 17?34."},{"key":"CR15","first-page":"16","volume":"26","author":"E. Cohen","year":"1994","unstructured":"E. Cohen: Polylog-time and near-linear work approximation scheme for undirected shortest paths,STOC 26 (1994), 16?26.","journal-title":"STOC"},{"key":"CR16","unstructured":"L. J. Cowen: On local representations of graphs and networks, PhD dissertation, MIT\/LCS\/TR-573, 1993."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF01193107","volume":"79","author":"L. Danzer","year":"1962","unstructured":"L. Danzer, andB. Gr\ufffdnbaum: \ufffdber zwei Probleme bez\ufffdglich konvexer K\ufffdrper von P. Erd?s und von V. L. Klee,Math. Zeitschr. 79 (1962), 95?99.","journal-title":"Math. Zeitschr."},{"key":"CR18","unstructured":"M. Deza, andM. Laurent: Applications of cut polyhedra, Liens-92-18, September 1992."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1090\/S0002-9947-1990-0974513-6","volume":"317","author":"M. Deza","year":"1990","unstructured":"M. Deza, andH. Maehara: Metric transforms and Euclidean embeddings,Trans. AMS 317 (1990), 661?671.","journal-title":"Trans. AMS"},{"key":"CR20","volume-title":"Pattern Classification and Scene Analysis","author":"R. O. Duda","year":"1973","unstructured":"R. O. Duda, andP. E. Hart:Pattern Classification and Scene Analysis, John Wiley and Sons, New York, 1973."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P. Frankl","year":"1988","unstructured":"P. Frankl, andH. Maehara: The Johnson-Lindenstrauss lemma and the sphericity of some graphs,J. Comb. Th. B 44 (1988), 355?362.","journal-title":"J. Comb. Th. B"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF02187899","volume":"3","author":"P. Frankl","year":"1988","unstructured":"P. Frankl, andH. Maehara: On the contact dimension of graphs,Discrete and Computational Geometry 3 (1988), 89?96.","journal-title":"Discrete and Computational Geometry"},{"key":"CR23","unstructured":"N. Garg: A deterministicO(logk)-approximation algorithm for the sparsest cut, preprint, 1995."},{"key":"CR24","first-page":"698","volume":"25","author":"N. Garg","year":"1993","unstructured":"N. Garg, V. V. Vazirani, andM. Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications,STOC 25 (1993), 698?707.","journal-title":"STOC"},{"key":"CR25","unstructured":"A. A. Giannopoulos: On the Banach-Mazur distance to the cube, to appear in:Geometric Aspects of Functional Analysis."},{"key":"CR26","first-page":"422","volume":"26","author":"M. X. Goemans","year":"1994","unstructured":"M. X. Goemans, andD. P. Williamson: 878-Approximation algorithms for MAX CUT and MAX 2SAT,STOC 26 (1994), 422?431.","journal-title":"STOC"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9947-1985-0776391-5","volume":"288","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham, andP. M. Winkler: On isometric embeddings of graphs,Trans. AMS 288 (1985), 527?536.","journal-title":"Trans. AMS"},{"key":"CR28","first-page":"A","volume":"25","author":"W. Holsztynski","year":"1978","unstructured":"W. Holsztynski: ? n as a universal metric space, Abstract 78T-G56,Notices AMS 25 (1978), A-367.","journal-title":"Notices AMS"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T. C. Hu","year":"1963","unstructured":"T. C. Hu: Multicommodity network flows,Operations Research 11 (1963), 344?360.","journal-title":"Operations Research"},{"key":"CR30","first-page":"1","volume":"27","author":"F. Jaeger","year":"1985","unstructured":"F. Jaeger: A survey of the cycle double cover conjecture,Annals of Discrete Math. 27 (1985), 1?12.","journal-title":"Annals of Discrete Math."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. B. Johnson","year":"1984","unstructured":"W. B. Johnson, andJ. Lindenstrauss: Extensions of Lipschitz mappings into a Hilbert space,Contemporary Mathematics 26 (1984), 189?206.","journal-title":"Contemporary Mathematics"},{"key":"CR32","series-title":"LNM","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BFb0078145","volume-title":"Geometric Aspects of Functional Analysis","author":"W. B. Johnson","year":"1987","unstructured":"W. B. Johnson, J. Lindenstrauss, andG. Schechtman: On Lipschitz embedding of finite metric spaces in low dimensional normed spaces, in:Geometric Aspects of Functional Analysis, (J. Lindenstrauss and V. Milman eds.) LNM 1267, Springer, Berlin-New York, 1987, 177?184."},{"key":"CR33","first-page":"2","volume":"35","author":"D. Karger","year":"1994","unstructured":"D. Karger, R. Motwani, andM. Sudan: Approximate graph coloring by semidefinite programming,FOCS 35 (1994), 2?13.","journal-title":"FOCS"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1090\/conm\/147\/01205","volume":"147","author":"A. K. Kelmans","year":"1993","unstructured":"A. K. Kelmans: Graph planarity and related topics,Contemporary Mathematics 147 (1993), 635?667.","journal-title":"Contemporary Mathematics"},{"key":"CR35","first-page":"726","volume":"31","author":"P. Klein","year":"1990","unstructured":"P. Klein, A. Agrawal, R. Ravi, andS. Rao: Approximation through multicommodity flow,FOCS 31 (1990), 726?737.","journal-title":"FOCS"},{"key":"CR36","first-page":"141","volume":"88","author":"P. Koebe","year":"1936","unstructured":"P. Koebe: Kontaktprobleme der konformen Abbildung, Berichte Verhande. S\ufffdchs. Akad. Wiss. Leipzig,Math.-Phys. Klasse 88 (1936), 141?164.","journal-title":"Math.-Phys. Klasse"},{"key":"CR37","first-page":"422","volume":"29","author":"T. Leighton","year":"1988","unstructured":"T. Leighton, andS. Rao: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms,FOCS 29 (1988), 422?431.","journal-title":"FOCS"},{"key":"CR38","unstructured":"M. Linial, N. Linial, N. Tishby, andG. Yona: Work in progress, 1995."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1017\/S0963548300000857","volume":"2","author":"N. Linial","year":"1993","unstructured":"N. Linial: Local-global phenomena in graphs,Combinatorics, Probability and Computing 2 (1993), 491?503.","journal-title":"Combinatorics, Probability and Computing"},{"key":"CR40","first-page":"577","volume":"35","author":"N. Linial","year":"1994","unstructured":"N. Linial, L. London, andYu. Rabinovich: The geometry of graphs and some of its algorithmic applications,FOCS 35 (1994), 577?591.","journal-title":"FOCS"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02122557","volume":"8","author":"N. Linial","year":"1988","unstructured":"N. Linial, L. Lov\ufffdsz, andA. Wigderson: Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91?102.","journal-title":"Combinatorica"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"N. Linial, D. Peleg, Yu. Rabinovich, andM. Saks: Sphere packing and local majorities in graphs, The 2nd Israel Symp. on Theory and Computing Systems (1993), 141?149.","DOI":"10.1109\/ISTCS.1993.253475"},{"key":"CR43","first-page":"320","volume":"2","author":"N. Linial","year":"1991","unstructured":"N. Linial, andM. Saks: Low diameter graph decompositions,SODA 2 (1991), 320?330. Journal version:Combinatorica 13 (1993), 441?454.","journal-title":"SODA"},{"key":"CR44","volume-title":"A Course in Combinatorics","author":"J. H. Lint van","year":"1992","unstructured":"J. H. van Lint, andR. M. Wilson:A Course in Combinatorics, Cambridge University Press, Cambridge, 1992."},{"key":"CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\ufffdsz","year":"1979","unstructured":"L. Lov\ufffdsz: On the Shannon capacity of a graph,IEEE Trans. Inf. Th. 25 (1979), 1?7.","journal-title":"IEEE Trans. Inf. Th."},{"key":"CR46","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0024-3795(89)90475-8","volume":"114?115","author":"L. Lov\ufffdsz","year":"1989","unstructured":"L. Lov\ufffdsz, M. Saks, andA. Schrijver: Orthogonal representations and connectivity of graphs,Linear Algebra Appl. 114?115 (1989), 439?454.","journal-title":"Linear Algebra Appl."},{"key":"CR47","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1090\/dimacs\/006\/14","volume-title":"Discrete and computational Geometry: papers from the DIMACS special year","author":"J. Matou?ek","year":"1991","unstructured":"J. Matou?ek: Computing the center of planar point sets, in:Discrete and computational Geometry: papers from the DIMACS special year, (J. E. Goodman, R. Pollack, and W. Steiger eds.) AMS, Providence, 1991, 221?230."},{"key":"CR48","first-page":"51","volume":"33","author":"J. Matou?ek","year":"1992","unstructured":"J. Matou?ek: Note on bi-Lipschitz embeddings into normed spaces,Comment. Math. Univ. Carolinae 33 (1992), 51?55.","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"CR49","first-page":"538","volume":"32","author":"G. L. Miller","year":"1991","unstructured":"G. L. Miller, S-H. Teng, andS. A. Vavasis: A unified geometric approach to graph separators,FOCS 32 (1991), 538?547.","journal-title":"FOCS"},{"key":"CR50","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/100216.100255","volume":"22","author":"G. L. Miller","year":"1990","unstructured":"G. L. Miller, andW. Thurston: Separators in two and three dimensions,STOC 22 (1990), 300?309.","journal-title":"STOC"},{"key":"CR51","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"D. Peleg, andA. Sch\ufffdffer: Graph spanners,J. Graph Theory 13 (1989), 99?116.","journal-title":"J. Graph Theory"},{"key":"CR52","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511662454","volume-title":"The Volume of Convex Bodies and Banach Space Geometry","author":"G. Pisier","year":"1989","unstructured":"G. Pisier:The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press, Cambridge, 1989."},{"key":"CR53","first-page":"691","volume":"25","author":"S. A. Plotkin","year":"1993","unstructured":"S. A. Plotkin, and\ufffd. Tardos: Improved bounds on the max-flow min-cut ratio for multicommodity flows,STOC 25 (1993), 691?697.","journal-title":"STOC"},{"key":"CR54","unstructured":"Yu. Rabinovich, andR. Raz: On embeddings of finite metric spaces in graphs with a bounded number of edges, in preparation."},{"key":"CR55","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(89)90142-8","volume":"74","author":"J. Reiterman","year":"1989","unstructured":"J. Reiterman, V. R\ufffddl, andE. ?i?ajov\ufffd: Geometrical embeddings of graphs,Discrete Mathematics 74 (1989), 291?319.","journal-title":"Discrete Mathematics"},{"key":"CR56","unstructured":"N. Robertson, andP. D. Seymour: Graph Minors I?XX,J. Comb. Th. B (1985-present)."},{"key":"CR57","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1287\/opre.14.6.1121","volume":"14","author":"B. Rothschild","year":"1966","unstructured":"B. Rothschild, andA. Whinston: Feasibility of two-commodity network flows,Operations Research 14 (1966), 1121?1129.","journal-title":"Operations Research"},{"key":"CR58","doi-asserted-by":"crossref","unstructured":"J. S. Salowe: On Euclidean graphs with small degree,Proc. 8th ACM Symp. Comp. Geom. (1992), 186?191.","DOI":"10.1145\/142675.142716"},{"key":"CR59","first-page":"647","volume":"1","author":"D. D. Sleator","year":"1988","unstructured":"D. D. Sleator, R. E. Tarjan, andW. P. Thurston: Rotation distance, triangulations, and hyperbolic geometry,J. AMS 1 (1988), 647?681.","journal-title":"J. AMS"},{"key":"CR60","unstructured":"W. P. Thurston: The finite Riemann mapping theorem, invited address, International Symposium in Celebration of the Proof of the Bieberbach Conjecture, Purdue University, 1985."},{"key":"CR61","series-title":"LMS Lecture Note Series","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: Knots, Colourings and Counting","author":"D. J. A. Welsh","year":"1993","unstructured":"D. J. A. Welsh:Complexity: Knots, Colourings and Counting, LMS Lecture Note Series 186, Cambridge University Press, Cambridge, 1993."},{"key":"CR62","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02579350","volume":"3","author":"P. M. Winkler","year":"1983","unstructured":"P. M. Winkler: Proof of the squashed cube conjecture,Combinatorica 3 (1983), 135?139.","journal-title":"Combinatorica"},{"key":"CR63","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0097-3165(86)90089-0","volume":"42","author":"H. S. Witsenhausen","year":"1986","unstructured":"H. S. Witsenhausen: Minimum dimension embedding of finite metric spaces,J. Comb. Th. A 42 (1986), 184?199.","journal-title":"J. Comb. Th. A"},{"key":"CR64","volume-title":"Convex Figures","author":"I. M. Yaglom","year":"1961","unstructured":"I. M. Yaglom, andV. G. Boltyanski\ufffd:Convex Figures, Holt, Rinehart and Winston, New York, 1961."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200757.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200757\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:20:45Z","timestamp":1734956445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01200757"],"URL":"https:\/\/doi.org\/10.1007\/bf01200757","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}