Every collinear set is free

Pat Morin

Carleton University

We show that if a planar graph $G$ has a plane straight-line embedding in which a subset $S$ of its vertices are collinear, then there is a planar straight-line embedding of $G$ in which all vertices in $S$ are on the $y$-axis and in which they have prescribed $y$-coordinates. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, untangling, universal point subsets, and related areas.

This talk will discuss the history and applications of this new result and sketch the proof. This is joint work with Vida Dujmovic, Fabrizio Frati, Daniel Goncalves, and Günter Rote.