%0 Journal Article
%T Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
%A David Eppstein
%J Computer Science
%D 2013
%I arXiv
%R 10.7155/jgaa.00319
%X 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+\epsilon}) for any \epsilon>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.
%U http://arxiv.org/abs/1308.0066v1