UNAM

On the number of planar graphs on a point set.

Csaba D. Tóth. Department of Mathematics and Statistics. University of Calgary. MIE. 25 DE MAYO. 4:30.

Cuándo 25/05/2011
de 16:30 a 18:00
Dónde Salicrup
Agregar evento al calendario vCal
iCal

Abstract: The number of planar graphs with n vertices has recently
been determined by Gimenez and Noy (2009). However, not all planar
graphs can be embedded with straight line edges on a single vertex
set of n points in the plane. Ajtai, Chvatal, Newborn, and
Szemeredi (1982) showed that there are at most c^n labeled planar
straight line graphs any n points in the plane. The constant c
has been improved from 10^{13} to 192 in the last 30 years, but
no tight upper bound is known. This talk will present recent upper and
lower bounds on the maximum number common geometric graphs on n
points in the plane, such as triangulations, spanning trees, and
Hamiltonian cycles.