Apr 12, 3:30pm, Wean 8220

Tobias Mueller, CWI Amsterdam

Line arrangements and geometric representations of graphs

Tobias Mueller, CWI Amsterdam

Line arrangements and geometric representations of graphs

Abstract:

A dot product representation of a graph assigns to each vertex s a
vector v(s) in R^k in such a way that v(s)^T v(t) > 1 if and only st
is an edge. Similarly, in a distance representation |v(s)-v(t)| < 1 if
and only if st is an edge.

I will discuss the solution of some open problems by Spinrad, Breu&Kirkpatrick and others on these and related geometric representations of graphs.

The proofs make use of a connection to oriented pseudoline arrangements, some results from algebraic geometry and the Colin de Verdiere parameter.