The ACO Seminar (2011-2012)
, 3:30pm, Wean 8220
, CWI Amsterdam
Line arrangements and geometric representations of
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
Back to the ACO home page