Enumeration of geometric graphs

November 12, 2010
3:45 pm - 5:00 pm
Bromfield-Pearson Building, Room 101

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 new 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.