The rectilinear local crossing number of K-n

摘要

The local crossing number of a drawing of a graph is the largest number of crossings on any edge of the drawing. In a rectilinear drawing of a graph, the vertices are points in the plane in general position and the edges are straight-line segments. The rectilinear local crossing number of the complete graph K-n, denoted by (lcr) over bar (Kn), is the minimum local crossing number over all rectilinear drawings of Kn. We determine lcr(Kn). More precisely, for every n is not an element of {8,14},