January 15 , 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.