Lectures and Colloquia during the semester

**13. November 2000**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9, 14195 Berlin

Seminarraum 005

**Lecture - 14.00 Uhr c.t.**

### Yinfeng Xu - Xi'an Jiaotong University, China

### Several Geometric MinMax Problems

*Abstract:*
In this talk, we mainly discuss three geometric minmax problems as

- minmax bridge between two seperated convex polygons
- minmax edge spanning tree of a planar point set
- minmax path spanning tree of a plannar pont set

Geometric structures and efficient algorithms for the optimal solutions of
the
problems are discussed and presented. At the end of the talk, some unsolved
geometric minmax problems are given.

**Colloquium - 16 Uhr s.t.**

### Hein van der Holst - Freie Universität Berlin

### High-dimensional flatness and knots in graphs

*Abstract:*
Motivated by the Colin de Verdiere invariant \mu(G) we discuss two
classes of graphs. The first class of graphs is defined as follows.
If G is a graph, let C_2(G) denote the complex obtained
from G by attaching to each circuit of G a disc. We say that
a graph is 4-flat if C_2(G) can be embedded in 4-space.
The suspension of a flat graph is a graph which is 4-flat. The graphs
that are obtained from K_7 and K_{3,3,1,1} by Y\Delta- and
\Delta Y-transformations are example of graphs which are not
4-flat. We conjecture that the 4-flat graphs are exactly
those graphs with \mu(G) \leq 5.

The second class is formed by those graphs which can be embedded
in 3-space such that no circuit is a nontrivial knot. Since this class
is closed under taking minors, one problem is to find graphs for which
such an embedding is not possible. Can we find a certificate which shows
that such an embedding is not possible (but not necessary the other way
around)? Generalizing work of Conway and Gordan, who showed how to find a
certificate for certain graphs in the case when one deals with the Arf
invariant, we show how to find a certificate in the case of a Vassiliev
invariant. (Some parts are joint work with R. Pendavingh.)

[top]