Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013
DOI: 10.7155/jgaa.00319
Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
Vol. 18, no. 2, pp. 211-231, 2014. Regular paper.
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(n7/6). No known input causes our algorithm to use area Ω(n1+ϵ) 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.
Submitted: December 2013.
Reviewed: February 2014.
Revised: February 2014.
Accepted: March 2014.
Final: April 2014.
Published: May 2014.
Communicated by Stephen K. Wismath and Alexander Wolff
article (PDF)
BibTeX