Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
arXiv:1308.0066 · doi:10.7155/jgaa.00319
Abstract
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 Ω(n^{1+ε}) for any ε>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.
12 pages, 8 figures. To appear at 21st Int. Symp. Graph Drawing, Bordeaux, 2013