## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, December 06, 2007, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Andreas Razen

## On the Number of Crossing-Free Geometric Graphs (Part I)

Let P be a set of n points in general position in the plane. We show that there is a constant eps > 0 such that a uniformly at random chosen crossing-free geometric graph on P contains in expectation at least a (1/2+eps)-fraction of the number of edges in a triangulation of P.

Hereby we derive (to our knowledge) the first non-trivial constant c>0 such that the number of crossing-free geometric graphs on P is at most c^n times more than the number of triangulations of P. By trivial we mean that the estimate clearly holds if we choose c such that c^n=2^M, where M is the number of edges in a triangulation of P. For a triangular convex hull of P, where M=3n-6, we obtain a constant c<7.98. As the previous upper bounds for the number of crossing-free geometric graphs on planar point sets were derived using the trivial 8^n factor, we can now slightly decrease this bound to O(343.11^n).

Joint work with Jack Snoeyink and Emo Welzl.

Information for students and suggested topics for student talks