| Hardcover ISBN: | 978-1-4704-5087-8 |
| Product Code: | COLL/65 |
| List Price: | $99.00 |
| MAA Member Price: | $89.10 |
| AMS Member Price: | $79.20 |
| eBook ISBN: | 978-1-4704-5354-1 |
| Product Code: | COLL/65.E |
| List Price: | $89.00 |
| MAA Member Price: | $80.10 |
| AMS Member Price: | $71.20 |
| Hardcover ISBN: | 978-1-4704-5087-8 |
| eBook: ISBN: | 978-1-4704-5354-1 |
| Product Code: | COLL/65.B |
| List Price: | $188.00 $143.50 |
| MAA Member Price: | $169.20 $129.15 |
| AMS Member Price: | $150.40 $114.80 |
| Hardcover ISBN: | 978-1-4704-5087-8 |
| Product Code: | COLL/65 |
| List Price: | $99.00 |
| MAA Member Price: | $89.10 |
| AMS Member Price: | $79.20 |
| eBook ISBN: | 978-1-4704-5354-1 |
| Product Code: | COLL/65.E |
| List Price: | $89.00 |
| MAA Member Price: | $80.10 |
| AMS Member Price: | $71.20 |
| Hardcover ISBN: | 978-1-4704-5087-8 |
| eBook ISBN: | 978-1-4704-5354-1 |
| Product Code: | COLL/65.B |
| List Price: | $188.00 $143.50 |
| MAA Member Price: | $169.20 $129.15 |
| AMS Member Price: | $150.40 $114.80 |
-
Book DetailsColloquium PublicationsVolume: 65; 2019; 444 ppMSC: Primary 05
Graphs 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. It is obvious that this geometry is crucial in engineering, for example, if you want to understand rigidity of frameworks and mobility of mechanisms. But even if there is no geometry directly connected to the graph-theoretic problem, a well-chosen geometric embedding has mathematical meaning and applications in proofs and algorithms. This book surveys a number of such connections between graph theory and geometry: among others, rubber band representations, coin representations, orthogonal representations, and discrete analytic functions. Applications are given in information theory, statistical physics, graph algorithms and quantum physics.
The book is based on courses and lectures that the author has given over the last few decades and offers readers with some knowledge of graph theory, linear algebra, and probability a thorough introduction to this exciting new area with a large collection of illuminating examples and exercises.
ReadershipGraduate students and researchers interested in graph theory.
-
Table of Contents
-
Chapters
-
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 Verdière number
-
Metric representations
-
Matching and covering in frameworks
-
Combinatorics of subspaces
-
Concluding thoughts
-
Appendix A. Linear algebra
-
Appendix B. Graphs
-
Appendix C. Convex bodies
-
-
Additional Material
-
Reviews
-
The material surveyed here runs broad and deep, and Lovász does a fine job keeping the forest and the trees in sight at all times. The connections illustrated here will enlighten anyone interested in the topics, but also emphasize the value — and the joy — of maintaining a broad toolset in mathematics.
Bill Wood, University of Northern Iowa -
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 -
László Lovász 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 Szemerédi, Rutgers University
-
-
RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Additional Material
- Reviews
- Requests
Graphs 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. It is obvious that this geometry is crucial in engineering, for example, if you want to understand rigidity of frameworks and mobility of mechanisms. But even if there is no geometry directly connected to the graph-theoretic problem, a well-chosen geometric embedding has mathematical meaning and applications in proofs and algorithms. This book surveys a number of such connections between graph theory and geometry: among others, rubber band representations, coin representations, orthogonal representations, and discrete analytic functions. Applications are given in information theory, statistical physics, graph algorithms and quantum physics.
The book is based on courses and lectures that the author has given over the last few decades and offers readers with some knowledge of graph theory, linear algebra, and probability a thorough introduction to this exciting new area with a large collection of illuminating examples and exercises.
Graduate students and researchers interested in graph theory.
-
Chapters
-
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 Verdière number
-
Metric representations
-
Matching and covering in frameworks
-
Combinatorics of subspaces
-
Concluding thoughts
-
Appendix A. Linear algebra
-
Appendix B. Graphs
-
Appendix C. Convex bodies
-
The material surveyed here runs broad and deep, and Lovász does a fine job keeping the forest and the trees in sight at all times. The connections illustrated here will enlighten anyone interested in the topics, but also emphasize the value — and the joy — of maintaining a broad toolset in mathematics.
Bill Wood, University of Northern Iowa -
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 -
László Lovász 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 Szemerédi, Rutgers University
