Description
Book SynopsisGraphs are usually represented as geometric objects drawn in the plane, consisting of nodes and curves connecting them. The main message of this book is that such a representation is not merely a way to visualize the graph, but an important mathematical tool.
Trade ReviewGeometric 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
Table of Contents
- 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
