A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, cr(G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating (cr)(G) appears to be a difficult problem, and deciding if (cr)(G) ≤ k is known to be NP-hard. In fact, the asymptotic behavior of (cr)(K_n) is still unknown. In this paper, we present a deterministic n~(2+o(1)) -time algorithm that finds a straight-line drawing of any n-vertex graph G with (cr)(G) + o(n~4) pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense n-vertex graph G, one can efficiently find a straight-line drawing of G with (1 + o(1))(cr)(G) pairs of crossing edges.
展开▼
