The geometry of graphs and some of its algorithmic applications

N. Alon, M. Katchalski, andW. R. Pulleyblank: Cutting disjoint disks by straight lines,Discrete and Computational Geometry 4 (1989), 239?243.

I. Alth�fer, G. Das, D. Dobkin, D. Joseph, andJ. Soares: On sparse spanners of weighted graphs,Discrete and Computational Geometry 9 (1993), 81?100.

E. M. Andreev: Convex polyhedra in Loba?evski� spaces,Mat. Sb. (N.S.) 81 (123) (1970), 445?478. English translation:Math. USSR Sb. 10 (1970), 413?440.

E. M. Andreev: Convex polyhedra of finite volume in Loba?evski� space,Mat. Sb. (N.S.) 83 (125) (1970), 256?260. English translation:Math. USSR Sb. 12 (1970), 255?259.

J. Arias-de-Reyna, andL. Rodr�gues-Piazza: Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces,Israel J. Math. 79 (1992), 103?111.

Y. Aumann, andY. Rabani: AnO(logk) approximate min-cut max-flow theorem and approximation algorithm, preprint, 1994.

B. Awerbuch, andD. Peleg: Sparse partitions,FOCS 31 (1990), 503?513.

L. Babai, andD. Frankl:Linear Algebra Methods in Combinatorics, Preliminary Version 2, Department of Computer Science, The University of Chicago, Chicago, 1992.

K. Ball: Isometric embedding inl p -spaces,Europ. J. Combinatorics 11 (1990), 305?311.

B. Berger: The fourth moment method,SODA 2 (1991), 373?383.

L. M. Blumenthal:Theory and Applications of Distance Geometry, Chelsea, New York, 1970.

J. Bourgain: On Lipschitz embedding of finite metric spaces in Hilbert space,Israel J. Math. 52 (1985), 46?52.

L. Carroll:Through the Looking-Glass and what Alice Found There, Chapter 6, Pan Books, London, 1947.

F. R. K. Chung: Separator theorems and their applications, in:Paths, Flows, and VLSI-Layout, (B. Korte, L. Lov�sz, H. J. Pr�mel, and A. Schrijver eds.) Springer, Berlin-New York, 1990, 17?34.

E. Cohen: Polylog-time and near-linear work approximation scheme for undirected shortest paths,STOC 26 (1994), 16?26.

L. J. Cowen: On local representations of graphs and networks, PhD dissertation, MIT/LCS/TR-573, 1993.

L. Danzer, andB. Gr�nbaum: �ber zwei Probleme bez�glich konvexer K�rper von P. Erd?s und von V. L. Klee,Math. Zeitschr. 79 (1962), 95?99.

M. Deza, andM. Laurent: Applications of cut polyhedra, Liens-92-18, September 1992.

M. Deza, andH. Maehara: Metric transforms and Euclidean embeddings,Trans. AMS 317 (1990), 661?671.

R. O. Duda, andP. E. Hart:Pattern Classification and Scene Analysis, John Wiley and Sons, New York, 1973.

P. Frankl, andH. Maehara: The Johnson-Lindenstrauss lemma and the sphericity of some graphs,J. Comb. Th. B 44 (1988), 355?362.

P. Frankl, andH. Maehara: On the contact dimension of graphs,Discrete and Computational Geometry 3 (1988), 89?96.

N. Garg: A deterministicO(logk)-approximation algorithm for the sparsest cut, preprint, 1995.

N. Garg, V. V. Vazirani, andM. Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications,STOC 25 (1993), 698?707.

A. A. Giannopoulos: On the Banach-Mazur distance to the cube, to appear in:Geometric Aspects of Functional Analysis.

M. X. Goemans, andD. P. Williamson: 878-Approximation algorithms for MAX CUT and MAX 2SAT,STOC 26 (1994), 422?431.

R. L. Graham, andP. M. Winkler: On isometric embeddings of graphs,Trans. AMS 288 (1985), 527?536.

W. Holsztynski: ? n as a universal metric space, Abstract 78T-G56,Notices AMS 25 (1978), A-367.

T. C. Hu: Multicommodity network flows,Operations Research 11 (1963), 344?360.

F. Jaeger: A survey of the cycle double cover conjecture,Annals of Discrete Math. 27 (1985), 1?12.

W. B. Johnson, andJ. Lindenstrauss: Extensions of Lipschitz mappings into a Hilbert space,Contemporary Mathematics 26 (1984), 189?206.

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.

D. Karger, R. Motwani, andM. Sudan: Approximate graph coloring by semidefinite programming,FOCS 35 (1994), 2?13.

A. K. Kelmans: Graph planarity and related topics,Contemporary Mathematics 147 (1993), 635?667.

P. Klein, A. Agrawal, R. Ravi, andS. Rao: Approximation through multicommodity flow,FOCS 31 (1990), 726?737.

P. Koebe: Kontaktprobleme der konformen Abbildung, Berichte Verhande. S�chs. Akad. Wiss. Leipzig,Math.-Phys. Klasse 88 (1936), 141?164.

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.

M. Linial, N. Linial, N. Tishby, andG. Yona: Work in progress, 1995.

N. Linial: Local-global phenomena in graphs,Combinatorics, Probability and Computing 2 (1993), 491?503.

N. Linial, L. London, andYu. Rabinovich: The geometry of graphs and some of its algorithmic applications,FOCS 35 (1994), 577?591.

N. Linial, L. Lov�sz, andA. Wigderson: Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91?102.

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.

N. Linial, andM. Saks: Low diameter graph decompositions,SODA 2 (1991), 320?330. Journal version:Combinatorica 13 (1993), 441?454.

J. H. van Lint, andR. M. Wilson:A Course in Combinatorics, Cambridge University Press, Cambridge, 1992.

L. Lov�sz: On the Shannon capacity of a graph,IEEE Trans. Inf. Th. 25 (1979), 1?7.

L. Lov�sz, M. Saks, andA. Schrijver: Orthogonal representations and connectivity of graphs,Linear Algebra Appl. 114?115 (1989), 439?454.

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.

J. Matou?ek: Note on bi-Lipschitz embeddings into normed spaces,Comment. Math. Univ. Carolinae 33 (1992), 51?55.

G. L. Miller, S-H. Teng, andS. A. Vavasis: A unified geometric approach to graph separators,FOCS 32 (1991), 538?547.

G. L. Miller, andW. Thurston: Separators in two and three dimensions,STOC 22 (1990), 300?309.

D. Peleg, andA. Sch�ffer: Graph spanners,J. Graph Theory 13 (1989), 99?116.

G. Pisier:The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press, Cambridge, 1989.

S. A. Plotkin, and�. Tardos: Improved bounds on the max-flow min-cut ratio for multicommodity flows,STOC 25 (1993), 691?697.

Yu. Rabinovich, andR. Raz: On embeddings of finite metric spaces in graphs with a bounded number of edges, in preparation.

J. Reiterman, V. R�dl, andE. ?i?ajov�: Geometrical embeddings of graphs,Discrete Mathematics 74 (1989), 291?319.

N. Robertson, andP. D. Seymour: Graph Minors I?XX,J. Comb. Th. B (1985-present).

B. Rothschild, andA. Whinston: Feasibility of two-commodity network flows,Operations Research 14 (1966), 1121?1129.

J. S. Salowe: On Euclidean graphs with small degree,Proc. 8th ACM Symp. Comp. Geom. (1992), 186?191.

D. D. Sleator, R. E. Tarjan, andW. P. Thurston: Rotation distance, triangulations, and hyperbolic geometry,J. AMS 1 (1988), 647?681.

W. P. Thurston: The finite Riemann mapping theorem, invited address, International Symposium in Celebration of the Proof of the Bieberbach Conjecture, Purdue University, 1985.

D. J. A. Welsh:Complexity: Knots, Colourings and Counting, LMS Lecture Note Series 186, Cambridge University Press, Cambridge, 1993.

P. M. Winkler: Proof of the squashed cube conjecture,Combinatorica 3 (1983), 135?139.

H. S. Witsenhausen: Minimum dimension embedding of finite metric spaces,J. Comb. Th. A 42 (1986), 184?199.

I. M. Yaglom, andV. G. Boltyanski�:Convex Figures, Holt, Rinehart and Winston, New York, 1961.