[home] - [up] |
Abstract: Given a finite set P of points in the plane, a geometric graph on P has P as its vertex set and the edges are realized by straight segments. We consider crossing-free geometric graphs of various types, e.g. triangulations, perfect matchings or spanning cylces, and we are interested in the number of such graphs that exist on P.
If P is in convex position, then these numbers are determined by the number of points in P (and invoke the Catalan Numbers). Here our goal is to derive bounds on how many such crossing-free graphs (of various types) a set of n points can allow at most. All bounds are of the form c^n and the crux of the matter is to get c as small as possible.
This reports on joint work with Micha Sharir.
Colloquium - 16:00
Abstract: Generic orthogonal surfaces are in relation with Scarf-Complexes and are rather well understood. In the non-generic case, it is much harder to ensure that the surface has a nice combinatorial structure.
We examine some properties of orthogonal surfaces that are less restrictive than genericity but still allow us to draw some conclusions.
For non-degenerate and rigid orthogonal surfaces, we present some results (and some more open problems) concerning the poset of characteristic points.