#
Monday Lecture and Colloquium

**January 15 , 2007**

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

###
Imre Barany - Budapest and London

###
On the power of linear dependences

*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**

###
Mareike Massow - Technische Universität Berlin

###
Parameters of Bar k-Visibility Graphs

*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.

Letzte Aktualisierung:
20.12.2006