Geometric thickness in a grid

AbstractThe 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 O(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 O(mlog3nloglogn) time (with high probability)