Monday, June 17
8:30 AM
Mudd Hall Auditorium

Chair: Leslie Hall, The Johns Hopkins University

IP1
Sphere Representations and the Colin de Verdiere Number of a Graph

Colin de Verdiere introduced a fascinating graph invariant mu. The invariant, whose definition was linear-algebraic, generated considerable interest. One of the reasons for this interest was that the invariant was the first linear-algebraic graph invariant that related to topological properties of graphs. In particular, mu le 3 characterizes planar graphs.

The speaker will present a survey of several recent developments concerning Colin de Verdiere's invariant. In particular, he will discuss a surprising connection with a classical theorem of Koebe on representations of planar graphs by touching circles, and a theorem of Cauchy on the rigidity of convex polytopes in 3-space, and use this connection to characterize the cases when mu is close to n, the number of nodes. This leads to the study of representations of graphs that generalize Koebe's construction (representations by orthogonal circles, for example). We also describe a key lemma of Van der Holst, and show how it leads to a number of interesting related linear algebraic invariants, introduced by Van der Holst, Schrijver and Laurent, and others.

Laszlo Lovasz
Department of Computer Science
Yale University

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index

MEM, 3/21/96