# Jerusalem Mathematics Colloquium

Thursday, 6 May 1999, 4:00 pm

Mathematics Bldg., lecture hall 2

##

Professor Laszlo Lovasz

(Yale University)

"Planar and linkless embeddings of graphs, and linear algebra"

** Abstract: **

To represent a graph in geometric way is a very natural and old
problem. For example, it was proved by Steinitz early in this century
that every 3-connected planar graph can be represented as the graph of
vertices and edges of a (3-dimensional) polytope.

Representability of a graph in various geometric fashions turns out to
be closely related to a number of basic properties of the graph.
Moreover, computing these representations often helps in the design of
algorithms for purely graph-theoretic problems.

With Lex Schrijver, we studied geometric representations that can be
derived from a spectral invariant of a graph introduced by
Colin de Verdi\`ere. For a planar graph, for example, one obtains
two representations which are "dual" to each other in some sense. Since
linkless embeddability in 3-space can also be characterized
in terms of this invariant, one hopes that pushing these methods
further one can algorithmically construct linkless embeddings (provided
such an embedding exists).

Coffee, Cookies, Company at the faculty lounge at 3:30.

List of talks, 1998-99

List of talks, 1997-98