Drawing Arrangement Graphs in Small Grids, or How to Play PlanarityEppstein, David (2013) Drawing Arrangement Graphs in Small Grids, or How to Play Planarity. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 436-447(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_38). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_38
AbstractWe 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.
Actions (login required)
|