Obstacle Numbers of Graphs


Meeting Time: Oct. 26, 2010, 2:00-2:50pm

Abstract: Arrange some vertices in the plane, and some polygon "obstacles", and construct a graph by drawing a straight line edge between vertices whenever it doesn't intersect an obstacle. Which graphs can be constructed in this way? Given a graph, how many obstacles do you need? What if the obstacles are convex polygons? In this talk we'll answer these questions using some surprising connections to a few different topics in graph theory. We'll also pose a number of questions which are still open. This work was done with undergraduate students in the Willamette Valley REU program.