Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Higashikawa, Yuya; Katoh, Naoki; Kobayashi, Yuki
• Is Part Of: International journal of computer mathematics. Volume 8:Issue 1(2023)
• Page Start: 67
• Page End: 79
• Publication Date: 2023-01-02
• Subjects: Laman graphs -- sparse and tight graphs -- plane graphs -- geometric graphs -- edge crossings; 68U05 -- 05C10 -- 05C90 -- 68R10; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2023.2184723
• Languages: English
• ISSNs: 2379-9927

Abstract

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).