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