### 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

Abstract:
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