DIMACS - Graduate Student Combinatorics Seminar

Title: Compatible Geometric Matchings

Speaker: Elizabeth Kupin, Rutgers University

Date: Wednesday, March 23, 2011 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Generally in graph theory we distinguish between a graph and a drawing, or embedding of the graph into the plane. In geometric graph theory, however, we work with a fixed drawing of a graph, and investigate its geometric properties. In particular, we'll be interested in planar, straight-line embeddings of perfect matchings. This is essentially a disjoint set of line segments. Some basic questions we could ask are does every set of 2n points in the plane have a straight line perfect matching? Can there be more than one? If we don't allow matchings to cross each other (in addition to not crossing themselves), how many can there be? These basic questions lead up to a beautiful open problem, that I will present some partial results on.

Graduate Student Combinatorics Seminars