The ACO Seminar (2011-2012)

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.