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.