January 15 , 2007
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
I will talk about an old result, the so called
vector-sum theorem and plan to explain how linear algebra
can help solving various geometric problems. Several
examples will illustrate the power of this technique.
Colloquium - 16:00
Bar k-Visibility Graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can traverse up to k bars. These graphs interpolate between the two well- known graph classes of Bar Visibility Graphs and Interval Graphs. They were introduced by Dean, Evans, Gethner, Laison, Safari and Trotter in 2005.
Dean et al. conjectured that Bar 1-Visibility Graphs are the union of at most two planar graphs, i.e., that they have thickness at most 2. We construct a Bar 1-Visibility Graph with thickness 3, disproving their conjecture. For a special case of Bar 1-Visibility Graphs we present an algorithm partitioning the edges into two planar graphs, showing that for this class the thickness is indeed bounded by 2.
In this talk, the mentioned graph classes will be introduced with some of their known properties and a stress on the thickness results. The results are joint work with Stefan Felsner and have been presented on the Graph Drawing 2006.