Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs
Yuya Higashikawa, Naoki Katoh, Yuki Ohdaira Kobayashi · International Journal of Computer Mathematics Computer Systems Theory · 2023
We investigate the Euclidean minimum weight Laman graph on a planar point set P, MLG(P) for short. Bereg et al. (2016) studied geometric properties of MLG(P) and showed that the upper and lower bounds for the total number of edge crossings in MLG(P) are 6|P|−9 and |P|−3, respectively. In this paper, we improve these upper and lower bounds to 2.5|P|−5 and (1.25−ε)|P| for any ε>0, respectively. For improving the upper bound, we introduce a novel counting scheme based on some geometric observations. We also propose an O(|P|2) time algorithm for computing MLG(P), which was regarded as one of interesting future works by Bereg et al. (2016).