Graphs and Geometry

Laszlo Lovasz, Eotvos Lorand University, Budapest, Hungary, and Hungarian Academy of Sciences, Budapest, Hungary.

Why are geometric representations interesting? Planar graphs Rubber bands Discrete harmonic functions Coin representation Square tilings Discrete analytic functions Discrete analytic functions: Statistical physics Adjacency matrix and its square Orthogonal representations: Dimension Orthogonal representations: The smallest cone Orthogonal representations: Quantum physics Semidefinite optimization Stresses Rigidity and motions of frameworks The Colin de Verdiere number Metric representations Matching and covering in frameworks Combinatorics of subspaces Concluding thoughts Appendix A: Linear algebra Appendix B: Graphs Appendix C: Convex bodies Bibliography Author index Subject index

Geometric representations of graphs lead to significant insights in the study of graph properties and their algorithmic aspects. This book is a thorough study of the subject written by the pioneer of many of the results in the area. It is a fascinating manuscript written by a superb mathematician who is also a fantastic expositor." - Noga Alon, Princeton University and Tel Aviv University "A beautiful book, rich in intuition, insights, and examples, from one of the masters of combinatorics, geometry, and graph theory. This book presents old friends of graph theory in a new light and introduces more recent developments, providing connections to many areas in combinatorics, analysis, algorithms, and physics. Those of us who know graph theory still have much to learn from this presentation; for those who are new to the field, the book is a wonderful gift and invitation to participate." - Jennifer Chayes, Microsoft Research "Laszlo Lovasz is one of the most prominent experts in discrete mathematics. The book is unique and inspiring for students and researchers as well. The author succeeded to show the wealth and beauty of the subject." - Endre Szemeredi, Rutgers University