Drawing Arrangement Graphs in Small Grids, or How to Play Planarity

Eppstein, 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.

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.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.070 Area / Edge Length P Styles > P.720 Straight-line
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1395

Actions (login required)

View Item