## 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: Tuesday, November 04, 2008, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Andreas Razen

## Counting Crossing-Free Geometric Graphs with Exponential Speed-Up (Part I)

For a set $P$ of $n$ points in the plane in general position we show that the number of crossing-free geometric graphs on $P$ is always a fixed exponential in $n$ more than the number of triangulations, while the number of graphs may still be computed in time necessary to enumerate all triangulations on $P$.

Joint work with Emo Welzl.

Information for students and suggested topics for student talks