The rectilinear local crossing number of K_n

2015/08/31 by Bernardo M. Ábrego, Ábrego, Bernardo M., Silvia Fernández‐Merchant +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1508.07926

Abstract

We determine \rmlcr(K_n), the rectilinear local crossing number of the complete graph K_n for every n. More precisely, for every n ∉ \8, 14 \, \rmlcr(K_n)=\lceil (1)/(2) ( n-3-\lceil (n-3)/(3) \rceil ) \lceil (n-3)/(3) \rceil \rceil, \rmlcr(K₈)=4, and \rmlcr(K₁₄)=15.

Cited by

• On Grundy indices for complete geometric graphs

Related

• A linear upper bound on the rectilinear crossing number
• On the k-planar local crossing number
• The crossing numbers of K_n,n-nK₂, K_n× P₂, K_n× P₃ and K_n× C₄
• On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs
• Computational search of small point sets with small rectilinear crossing number