Geometric thickness in a grid

The geometric thickness of a graph is the minimum number of layers such that the graph can be drawn in the plane with edges as straight-line segments, and with each edge assigned to a layer so that no two edges in the same layer cross. We consider a variation on this theme in which each edge is allowed one bend. We prove that the vertices of an n-vertex m-edge graph can be positioned in a ⌈√n⌈ × ⌈√n⌈ grid and the edges assigned to script O sign(√m) layers, so that each edge is drawn with at most one bend and no two edges on the same layer cross. The proof is a 2-dimensional generalisation of a theorem of Malitz (J. Algorithms 17(1) (1994) 71-84) on book embeddings. We obtain a Las Vegas algorithm to compute the drawing in script O sign(m log3nloglog n) time (with high probability).