Graphs and Matroids Seminar - Alan Arroyo

Title: Geometric drawings of graphs (Part I)

Abstract:

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.