Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs. Issue 1 (2nd January 2023) - Higashikawa, Yuya; Katoh, Naoki; Kobayashi, Yuki
Abstract : We investigate the Euclidean minimum weight Laman graph on a planar point set P, M L G ( P ) for short. Bereg et al. (2016) studied geometric properties of M L G ( P ) and showed that the upper and lower bounds for the total number of edge crossings in M L G ( 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 M L G ( P ), which was regarded as one of interesting future works by Bereg et al. (2016).