The rectilinear local crossing number of K-n

作者：Abrego Bernardo M^*; Fernandez Merchant Silvia

来源：Journal of Combinatorial Theory - Series A, 2017, 151: 131-145.

DOI：10.1016/j.jcta.2017.04.003

• Local crossing number
• Complete graph
• Geometric drawing
• Rectilinear drawing
• Rectilinear crossing number
• Balanced partition

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},
(lcr) over bar (K-n)= inverted right perpendicular1/2( n-3- inverted right perpendicular n-3/3inverted left perpendicular) inverted right perpendicular n-3/3inverted left perpendicular inverted left perpendicular,
(lcr) over bar (K-8) = 4, and (lcr) over bar (K-14) = 15.

• 出版日期2017-10