37
Views
0
CrossRef citations to date
0
Altmetric
27th International Computing and Combinatorics Conference (Selected Papers from COCOON 2021)

Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs

, &
Pages 67-79 | Received 18 Feb 2022, Accepted 09 Feb 2023, Published online: 19 Mar 2023
 

Abstract

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

MATHEMATICS SUBJECT CLASSIFICATIONS:

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.