Improving Upper and Lower Bounds for the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs

We investigate the total number of edge crossings (i.e., the crossing number) of the Euclidean minimum weight Laman graph \(\mathsf {MLG}(P)\) on a planar point set P. Bereg et al. (2016) showed that the upper and lower bounds for the crossing number of \(\mathsf {MLG}(P)\) are \(6|P|-9\) and \(|P|-3\), respectively. In this paper, we improve these upper and lower bounds given by Bereg et al. (2016) to \(2.5|P|-5\) and \((1.25-\varepsilon )|P|\) for any \(\varepsilon > 0\), respectively. Especially, for improving the upper bound, we introduce a novel counting scheme based on some geometric observations.