Hardcover ISBN:  9781470450878 
Product Code:  COLL/65 
List Price:  $99.00 
MAA Member Price:  $89.10 
AMS Member Price:  $79.20 
eBook ISBN:  9781470453541 
Product Code:  COLL/65.E 
List Price:  $89.00 
MAA Member Price:  $80.10 
AMS Member Price:  $71.20 
Hardcover ISBN:  9781470450878 
eBook: ISBN:  9781470453541 
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:  9781470450878 
Product Code:  COLL/65 
List Price:  $99.00 
MAA Member Price:  $89.10 
AMS Member Price:  $79.20 
eBook ISBN:  9781470453541 
Product Code:  COLL/65.E 
List Price:  $89.00 
MAA Member Price:  $80.10 
AMS Member Price:  $71.20 
Hardcover ISBN:  9781470450878 
eBook ISBN:  9781470453541 
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 graphtheoretic problem, a wellchosen 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 graphtheoretic problem, a wellchosen 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