Graphs and Matroids Seminar - Alan Arroyo

Thursday, September 14, 2017 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Geometric drawings of graphs (Part I)

Speaker: Alan Arroyo
Affiliation: University of Waterloo
Room: MC 5479


This is the first of two talks about drawings of graphs that arise from geometry.

Part I: Understanding rectilinear drawings.

Fáry's Theorem states that every planar embedding of a graph is equivalent to a rectilinear drawing (where edges are straight line segments). This surprising result has nice generalizations that allow some edges to cross, however, in general it is hard to tell when a drawing can be realized using straight line segments. I will talk about our recent efforts to understand why, under some circumstances, drawings can be straightened.