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

Abstract

We investigate the Euclidean minimum weight Laman graph on a planar point set P, $\mathsf{M}\mathsf{L}\mathsf{G}(P)$ for short. Bereg et al. (2016) studied geometric properties of $\mathsf{M}\mathsf{L}\mathsf{G}(P)$ and showed that the upper and lower bounds for the total number of edge crossings in $\mathsf{M}\mathsf{L}\mathsf{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-\epsilon )|P|$ for any $\epsilon >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 $\mathsf{M}\mathsf{L}\mathsf{G}(P)$, which was regarded as one of interesting future works by Bereg et al. (2016).

KEYWORDS:

• Laman graphs
• sparse and tight graphs
• plane graphs
• geometric graphs
• edge crossings

MATHEMATICS SUBJECT CLASSIFICATIONS:

• 68U05
• 05C10
• 05C90
• 68R10

Acknowledgments

A preliminary version of this paper appeared in the proceedings of COCOON 2021 [7].

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 [2] corresponds to Lemma 2.6(i)(ii).

3 Another terminology constrained geometric thickness of a graph is used in [3].