CS 269S, Spring 2013: Theory Seminar
Bren Hall, Room 1420, 1pm
May 17, 2013:

Universal Point Sets

Jack Cheng

A set of points on the plane is an n-universal point set if every planar graph on n vertices can be embedded in the set without creating edge crossings. I will discuss some previously known results about universal point sets. Then I will present a new construction based on 213-superpatterns that gives a factor of two improvement over currently known upper bounds on the size of universal point sets. This is joint work with Bannister, Devanny, and Eppstein.