Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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