Abstract
In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images.
In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include:
-
•
A simple, unified approach to a number of problems on multicommodity flows, including the Leighton-Rao Theorem [37] and some of its extensions. We solve an open question in this area, showing that the max-flow vs. min-cut gap in thek-commodities problem isO(logk). Our new deterministic polynomial-time algorithm finds a (nearly tight) cut meeting this bound.
-
•
For graphs embeddable in low-dimensional spaces with a small distortion, we can find low-diameter decompositions (in the sense of [7] and [43]). The parameters of the decomposition depend only on the dimension and the distortion and not on the size of the graph.
-
•
In graphs embedded this way, small balancedseparators can be found efficiently.
Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6.
Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper appered in FOCS '94 ([40]).
Supported in part by grants from the Israeli Academy of Sciences, the Binational Science Foundation Israel-USA and the Niedersachsen-Israel Research Program.
Rights and permissions
About this article
Cite this article
Linial, N., London, E. & Rabinovich, Y. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215–245 (1995). https://doi.org/10.1007/BF01200757
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01200757