Abstract
We investigate the Euclidean minimum weight Laman graph on a planar point set P, for short. Bereg et al. (2016) studied geometric properties of and showed that the upper and lower bounds for the total number of edge crossings in are and , respectively. In this paper, we improve these upper and lower bounds to and for any , respectively. For improving the upper bound, we introduce a novel counting scheme based on some geometric observations. We also propose an time algorithm for computing , which was regarded as one of interesting future works by Bereg et al. (2016).
Acknowledgments
A preliminary version of this paper appeared in the proceedings of COCOON 2021 [Citation7].
Disclosure statement
No potential conflict of interest was reported by the author(s).
Notes
1 Throughout the paper, for two points p, q, we abuse the notation pq to denote the line segment between p and q or the length of itself, depending on the context.
2 Lemma 4.1 in [Citation2] corresponds to Lemma 2.6(i)(ii).
3 Another terminology constrained geometric thickness of a graph is used in [Citation3].