Approximating the rectilinear crossing number

摘要

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) over bar (G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating (cr) over bar (G) appears to be a difficult problem, and deciding if (cr) over bar (G) <= k is known to be NP-hard. In fact, the asymptotic behavior of (cr) over bar (K-n) is still unknown.