CS 269S, Fall 2013: Theory Seminar
Bren Hall, Room 1422, 1pm
October 4, 2013:

Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity

David Eppstein

We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n^{7/6}). No known input causes our algorithm to use area Omega(n^{1+eps}) for any eps > 0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle.