1. Introduction
A bar-joint framework is one of the main frameworks studied in combinatorial rigidity theory. It consists of rigid bars and rotatable joints. We can discuss the bar-joint framework as a graph of combinatorial theory by mapping each joint to a vertex and each bar to a straight-line edge [1]. One of the most fundamental results in combinatorial rigidity theory asserts that given a graph \(G\) realized on a generic point set in the plane (i.e., the set of the coordinates is algebraically independent over the rational field), \(G\) is rigid if and only if \(G\) contains a spanning Laman subgraph [2]. A graph \(G = (V,E)\) is a Laman graph if it satisfies \(|E|=2|V|-3\) and \(|E(H)| \leq 2|V(H)| - 3\) for any subgraph \(H\) of \(G\) with \(E(H) \neq \emptyset\). Laman graphs appear in a wide range of applications, not only statics but also mechanical design such as linkages, design of CAD systems, analysis of protein flexibility, and sensor network localization [3], [4].
The concept of the sparsity condition of a Laman graph is generalized to a \((k,\ell)\text{-}\mathit{tight\ graph}\) (see, e.g., [5]). The class of \((k,\ell)\text{-tight graph}\)s includes important graphs: a Laman graph is a \((2,3)\text{-tight graph}\), and a spanning tree being studied in various fields is a \((1,1)\text{-tight graph}\). Furthermore, it is known that any \((k,k)\)-tight graph can be decomposed into \(k\) edge-disjoint spanning trees [6], [7], and \((6,6)\text{-tight graph}\)s appear in the necessary and sufficient condition of realization as an infinitesimally rigid body-hinge framework [8].
In two-dimensional generic bar-joint frameworks, the class of \((2,\ell)\text{-tight graph}\)s, including Laman graphs, plays an important role. For example, a \((2,2)\text{-tight graph}\) is minimally rigid when the joints are constrained to lie on the surface of a cylinder (since this surface allows two independent rigid-body motions) [9].
In this paper, we focus on the edge crossing of Laman graphs and \((2,2)\text{-tight graph}\)s. In order to realize a graph as a bar-joint framework on the plane in the real world, it is important to consider its edge crossing. Thus, one of our concerns is the graphs that maximize the total number of edge crossings. Another concern is the graphs that maximize the geometric thickness. The geometric thickness of graph \(G\) is the smallest number of layers necessary to partition the edge set of \(G\) into layers so that no layers have edge crossing (see, e.g., [10]).
Thus, more specifically, we at first focus on the maximum total number of edge crossings and the maximum geometric thickness of the Euclidean minimum-weight Laman graphs. The Euclidean minimum-weight Laman graph on a point set \(P\), denoted by \(\textsf{MLG}(P)\), is the Laman graph with the minimum total edge length among all Laman graphs on \(P\). We also focus on those of the Euclidean minimum-weight \((2,2)\text{-tight graph}\)s, where the Euclidean minimum-weight \((k,\ell)\text{-}\mathit{tight\ graph}\) on \(P\), denoted by \((k,\ell)\textsf{-MTG}(P)\), is defined similarly as a generalization of \(\textsf{MLG}(P)\). Interestingly, while the Euclidean minimum-weight spanning tree on \(P\) is always planar (i.e., it has no edge crossings), \(\textsf{MLG}(P)\) may have some edge crossings (see e.g., Fig. 2).
Bereg et al. [11] showed many properties of \(\textsf{MLG}(P)\) for any semi-generic point set \(P\), e.g., 6-planarity, no three edges cross each other, and the implication \(\textsf{MLG}(P) \subseteq 1\textsf{-GG}(P)\) on the edges of the graphs, where \(1\textsf{-GG}(P)\) is a 1-Gabriel graph. From the 6-planarity of \(\textsf{MLG}(P)\), they showed that the upper bound for the maximum total number of edge crossings of \(\textsf{MLG}(P)\) is \(6|P|-9\). They also showed that the lower bound for the maximum total number of edge crossings of \(\textsf{MLG}(P)\) is \(|P|-3\). Later, Higashikawa et al. [12] improved the upper and lower bounds for the maximum total number of edge crossings of \(\textsf{MLG}(P)\) to \(2.5|P|-5\) and \((1.25-\epsilon)|P|\) for any \(\epsilon > 0\), respectively. Unfortunately, a gap between those bounds still exists. As for the maximum geometric thickness of \(\textsf{MLG}(P)\), since the geometric thickness of \(1\textsf{-GG}(P)\) is at most 4 [13], \(\textsf{MLG}(P)\subseteq 1\textsf{-GG}(P)\) in [11] implies that the upper bound for the maximum geometric thickness of \(\textsf{MLG}(P)\) is 4. On the other hand, its lower bound is 2 since \(\textsf{MLG}(P)\) may have some edge crossings. Thus, we also have a gap in the maximum geometric thickness.
Furthermore, the maximum total number of edge crossings and the maximum geometric thickness of \((k,\ell)\textsf{-MTG}(P)\) for general \(k\) and \(\ell\) is in our interest. Bereg et al. [11] showed that \((k,\ell)\textsf{-MTG}(P)\) is \((6k^2+4k-10)\)-planar. In other words, each edge of \((k,\ell)\textsf{-MTG}(P)\) crosses at most \((6k^2+4k-10)\) other edges. According to this result, it is easy to see that the total number of edge crossings of \((k,\ell)\textsf{-MTG}(P)\) is at most \((6k^2+4k-10)(k|P|-\ell)/2\). As Bereg et al. told in [11], this upper bound is not tight. In case \(k=2\) and \(\ell=3\), we can see the bound is \(22 |P| - 33\). There are many open questions regarding the maximum total number of edge crossings and the maximum geometric thickness of the \((k,\ell)\textsf{-MTG}(P)\). As a first step for general \(k\) and \(\ell\), we focus on \((2,3)\textsf{-MTG}(P)\) and \((2,2)\textsf{-MTG}(P)\).
Our contribution is as follows. At first, we improve the lower bound for the maximum total number of edge crossings of \(\textsf{MLG}(P)\). In other words, we show a semi-generic point set \(P\) that improve the lower bound. Our idea for the proof is based on the method by Higashikawa et al. [12]: arrange the same units on a circumference, where each unit consists of carefully positioned five points. We extend this method by alternately arranging two types of units on a circumference. Each of both units consists of eight points, and their arrangement is well determined so as to derive isomorphic Euclidean minimum-weight Laman graphs and not to interfere with each other. By alternately arranging these two types of units, we derive lower bound \((\frac{10}{7}-\epsilon)|P|\) for any \(\epsilon > 0\).
Our extended method has the possibility to derive a lower bound for general cases. To show the power of our method, we apply it to different \(\ell\). More precisely, we derive a lower bound for the maximum total number of edge crossings of \((2,2)\textsf{-MTG}(P)\) by regularly arranging different units made under the same design: Each unit differs in only one parameter regarding width, while all other parameters are the same for all units. By regularly arranging these units, we derive lower bound \((\frac{11}{6}-\epsilon)|P|\) for any \(\epsilon > 0\), while no lower bounds were known. Our results on \((2,3)\textsf{-MTG}(P)\) and \((2,2)\textsf{-MTG}(P)\) suggest that the maximum total number of edge crossings depends on parameter \(\ell\). Recall that the upper bound by Bereg et al. [11] was with parameter \(k\). Thus, we can open the door for the discussion with general \(k\) and \(\ell\).
We also address the lower bounds for the maximum geometric thickness of \(\textsf{MLG}(P)\) and \((2,2)\textsf{-MTG}(P)\). We use the edge-crossing graph (also called crossing dual graph) of a geometric graph \(G(P)\). Each vertex and edge of the edge-crossing graph corresponds to an edge of \(G(P)\) and the edge crossing of two edges of \(G(P)\), respectively. Interestingly, the chromatic number of the edge-crossing graph is equal to the geometric thickness of the original geometric graph \(G(P)\) [12]. We show a semi-generic point set \(P\) such that the edge-crossing graph of \(\textsf{MLG}(P)\) contains a cycle of odd length. Since this implies its chromatic number is at least 3, we can improve the lower bound to 3. In a similar way, we can also derive the same lower bound for the maximum geometric thickness of \((2,2)\textsf{-MTG}(P)\).
2. Preliminaries
2.1 Minimum-Weight (\(k\),\(\ell\))-Tight Graphs
A graph \(G = (V,E)\) is a \((k,\ell)\textit{-sparse graph}\) \((0\leq\ell\leq 2k-1)\) if it satisfies \(|E(H)| \leq k|V(H)| - \ell\) for any subgraph \(H\) of \(G\) with \(E(H) \neq \emptyset\), where \(E(H)\) denotes the set of edges of \(H\). A \((k,\ell)\text{-sparse graph}\) is a \((k,\ell)\text{-}\mathit{tight\ graph}\) if it has exactly \(k|V(G)|-\ell\) edges. In particular, \((1,1)\text{-tight graph}\), i.e., the graph for the case \(k = \ell = 1\), is called a spanning tree, and \((2,3)\text{-tight graph}\) is called a Laman graph.
A geometric graph \(G(P)=(P,E_\mathbf{p})\) on a planar point set \(P\) is obtained by embedding a graph \(G=(V,E)\) into a two-dimensional Euclidean plane by a bijection \(\mathbf{p}:V\to P\). Each vertex \(v_i \in V\) of graph \(G\) is mapped to a point \(\mathbf{p}(v_i)=p_i\), and each edge \((v_i,v_j) \in E\) is mapped to a line segment \(\mathbf{p}(v_i)\mathbf{p}(v_j) \in E_\mathbf{p}\). In this paper, we denote \({p_{i}}{p_{j}}\) as both the line segment \(\mathbf{p}(v_i)\mathbf{p}(v_j)\) and the edge \((v_i,v_j)\). The weight of edge \({p_{i}}{p_{j}}\) is defined as the Euclidean distance between two points \(p_{i}\) and \(p_{j}\), denoted by \(\|{p_{i}}{p_{j}}\|\).
The \((k,\ell)\text{-tight graph}\) with the minimum total edge weight among all \((k,\ell)\text{-tight graph}\)s on \(P\) is called the Euclidean minimum-weight \((k,\ell)\text{-}\mathit{tight\ graph}\) on \(P\), and denoted by \((k,\ell)\textsf{-MTG}(P)\). In case \(k = 2\) and \(\ell = 3\), (2,3)-MTG(P) is also called the Euclidean minimum-weight Laman graph on \(P\), and denoted by \(\textsf{MLG}(P)\). Throughout the paper, we assume that no three points in \(P\) are collinear and that all distances between two points in \(P\) are distinct, called semi-generic. From this assumption, given a semi-generic point set \(P\), we can uniquely obtain \(\textsf{MLG}(P)\) and \((k,\ell)\textsf{-MTG}(P)\).
2.2 \((k,\ell)\)-Sparsity Matroid
A matroid \(\mathcal{M}\) is an ordered pair \((E,\mathcal{L})\) consisting of a finite set \(E\) and a family \(\mathcal{L}\) of subsets of \(E\) satisfying the following conditions:
(C1) \(\emptyset \in \mathcal{L}\).
(C2) If \(X \in \mathcal{L}\) and \(X' \subseteq X\), then \(X' \in \mathcal{L}\).
(C3) If \(A\) and \(B\) are in \(\mathcal{L}\) and \(|A| < |B|\), then there is an element \(e \in B \setminus A\) satisfying \(A\cup \{e\} \in \mathcal{L}\).
A finite set \(E\) is a ground set of \(\mathcal{M}\). The members of \(\mathcal{L}\) are called independent. On the contrary, a subset of \(E\) that is not in \(\mathcal{L}\) is called dependent. A maximum independent set and a minimal dependent set in \(\mathcal{M}\) are called a basis and a circuit of \(\mathcal{M}\), respectively. It is known that all subsets of a circuit are independent.
Given a graph \(G=(V,E)\), let \(\mathcal{L}\) be the family of subsets of \(E\), where each of which induces a \((k,\ell)\)-sparse subgraph of \(G\). Then, a pair \((E,\mathcal{L})\) is known to be a matroid, called the \((k,\ell)\)-sparsity matroid [14]. Especially, a \((k,\ell)\)-sparsity matroid with \(k=2\) and \(\ell=3\) is also called two-dimensional rigidity matroid. If \(G\) is a complete graph, a basis of the \((k,\ell)\)-sparsity matroid induces a \((k,\ell)\text{-tight graph}\).
Lemma 1 (Proposition 5.3 [12]). Consider a matroid with ground set \(E\) whose elements are assigned distinct weights. Let \(e^*\) be the element with the maximum weight in a circuit in \(E\). Then, \(e^*\) is not included in any minimum weight basis of the matroid.
Lemma 2 (Lemma 2.2 [11]). Let P be a semi-generic point set in the plane, \(Q \subseteq P\), and \(a,b \in Q\). Also let \(E_{{a}{b}}(Q)\) be the set of edges \(\{ pq \mid p,q \in Q, p \neq q, \|pq\| < \|ab\| \}\). If there exists a subset of \(E_{{a}{b}}(Q)\) that induces a Laman graph on \(Q\), then \(ab \notin E(\textsf{MLG}(P))\) holds.
The above Lemma 2 by Bereg et al. [11] is a good tool for distinguishing whether an edge is in the \(\textsf{MLG}(P)\). The sketch of its proof is as follows. Given a semi-generic point set \(P\), let \(K(P)=(P,E)\) be the geometric complete graph on \(P\). Lemma 2 is obtained by applying Lemma 1 to a two-dimensional rigidity matroid, where the ground set is the edge set \(E\). As \(P\) is a semi-generic point set, all elements (i.e., edges) of \(E\) have distinct weights. The assumption of Lemma 2 says we have a Laman graph on \(Q\) that is induced by some subset \(E'\) of \(E_{{a}{b}}(Q)\). For any edge \(e\in E(K(Q)) \setminus E'\), if we add \(e\) to \(E'\), the resulting edge-induced graph \((Q,E'\cup \{e\})\) does not satisfy the definition of \((2,3)\text{-sparse graph}\). This means that edge set \(E'\cup\{e\}\) is not independent, i.e., it is dependent. Thus, \({a}{b} \in E(K(Q)) \setminus E'\) implies that \(E'\cup\{{a}{b}\}\) is dependent. As a circuit is a minimal dependent set, there exists a circuit \(E''\cup\{{a}{b}\}\) satisfying \(E''\subseteq E'\). By definition of \(E_{{a}{b}}(Q)\) in Lemma 2, \(\|e\|<\|{a}{b}\|\) holds for any \(e\in E_{{a}{b}}(Q)\). This means that, as \(E''\subseteq E' \subseteq E_{{a}{b}}(Q)\), edge \({a}{b}\) is the element with the maximum weight in the circuit \(E''\cup \{{a}{b}\}\). Therefore, Lemma 1 says \({a}{b}\) is not included in any minimum weight basis. As the minimum weight basis edge-induces the Euclidean minimum-weight Laman graph \(\textsf{MLG}(P)\), \(ab\notin E(\textsf{MLG}(P))\) holds.
By a similar argument with Lemma 2, we can extend the above lemma to the general case, i.e., \((k,\ell)\textsf{-MTG}(P)\) for general \(k\) and \(\ell\).
Lemma 3. Let P be a semi-generic point set in the plane, \(Q \subseteq P\), and \(a,b \in Q\). Also let \(E_{{a}{b}}(Q)\) be the set of edges \(\{ pq \mid p,q \in Q, p \neq q, \|pq\| < \|ab\| \}\). If there exists a subset of \(E_{{a}{b}}(Q)\) that induces a \((k,\ell)\text{-}\mathit{tight\ graph}\) on Q, then \(ab \notin E((k,\ell)\textsf{-MTG}(P))\) holds.
We can obtain Lemma 3 by replacing the two-dimensional rigidity matroid on the edge set of the geometric complete graph \(K(P)\) on \(P\) and Laman graphs in Lemma 2 by the \((k,\ell)\)-sparsity matroid on the edge set of \(K(P)\) and \((k,\ell)\text{-tight graph}\), respectively. As in Lemma 2, the ground set is \(E\) and all elements of \(E\) have distinct weight. The assumption of Lemma 3 says we have a \((k,\ell)\text{-tight graph}\) on \(Q\) that is induced by some subset \(E'\) of \(E_{{a}{b}}(Q)\). For any edge \(e\in E(K(Q)) \setminus E'\), if we add \(e\) to \(E'\), the resulting edge-induced graph \((Q,E'\cup \{e\})\) does not satisfy the definition of \((k,\ell)\text{-sparse graph}\) as in Lemma 2. This means that edge set \(E'\cup\{e\}\) is not independent, i.e., it is dependent. These statements are the same as in Lemma 2 even if we replace ‘Laman graph’ by ‘\((k,\ell)\text{-tight graph}\)’. Thus, \({a}{b} \in E(K(Q)) \setminus E'\) implies that \(E'\cup\{{a}{b}\}\) is dependent and there exists a circuit \(E''\cup\{{a}{b}\}\) satisfying \(E''\subseteq E'\). By definition of \(E_{{a}{b}}(Q)\) in Lemma 3, \(\|e\|<\|{a}{b}\|\) holds for any \(e\in E_{{a}{b}}(Q)\). This means that, as \(E''\subseteq E' \subseteq E_{{a}{b}}(Q)\), edge \({a}{b}\) is the element with the maximum weight in a circuit \(E''\cup \{{a}{b}\}\). Therefore, Lemma 1 says \({a}{b}\) is not included in any minimum weight basis. As the minimum weight basis edge-induces the \((k,\ell)\textsf{-MTG}(P)\), \(ab\notin E((k,\ell)\textsf{-MTG}(P))\) holds. We use this lemma to prove the lower bounds for the maximum total number of edge crossings of \((2,2)\textsf{-MTG}(P)\).
2.3 Geometric Thickness of Geometric Graphs
Our focus is the crossings of the edges in a geometric graph \(G(P) = (P, E)\). Two edges \(e\) and \(e'\) (\(\in E\)) are crossing if and only if they have a common point other than their both ends. We denote the total number of edge crossings in \(G(P)\) by \(\sigma(G(P))\). The geometric thickness of \(G(P)\) is defined as the minimum positive integer \(t\) satisfying the following conditions:
- \(\cup_{i=1}^t{E_i}=E\).
- For any integer \(i\) \((1\leq i\leq t)\), geometric graph \(G_i(P)=(P,E_i)\) is non-crossing (i.e., \(G_i(P)\) is a plane graph).
Suppose that we are given a geometric graph \(G(P)\) with geometric thickness \(t\), and that we partition \(E\) into \(t-1\) edge sets \(E_1,E_2,\ldots,E_{t-1}\). Then, at least one geometric graph \(G_i(P) =(P, E_i)\) has edge crossing.
We introduce edge-crossing graphs of geometric graphs to understand the geometric thickness. Given a geometric graph \(G(P) =(P, E)\), its edge-crossing graph \((W,F)\) is defined as follows: each vertex \(e \in W\) corresponds to edge \(e \in E\), and edge \((e,e')\) is in \(F\) if and only if edges \(e\) and \(e'\) cross each other in \(G(P)\). The following relationship exists between the geometric thickness of a geometric graph and the chromatic number of the edge-crossing graph.
Lemma 4 ([12]). The geometric thickness of a geometric graph \(G(P)\) is equal to the chromatic number of the edge-crossing graph of \(G(P)\).
3. Lower Bounds
In this section, we show the lower bounds for the maximum geometric thickness and the maximum total number of edge crossings of \(\textsf{MLG}(P)\) and \((k,\ell)\textsf{-MTG}(P)\) by giving semi-generic point sets \(P\), respectively. To improve the lower bound for the maximum total number of edge crossings, we use units consisting of several points. For \(\textsf{MLG}(P)\), the lower bound is derived by counting the total number of edge crossings of MLG on a point set with alternately arranged two types of units. For \((2,2)\textsf{-MTG}(P)\), we consider a point set regularly arranging different units made under the same design. We also improve the lower bound for the maximum geometric thickness by showing that the bounds of both \(\textsf{MLG}(P)\) and \((2,2)\textsf{-MTG}(P)\) is 3. We focus on \(\textsf{MLG}(P)\) in Sect. 3.1, and \((2,2)\textsf{-MTG}(P)\) in Sect. 3.2.
3.1 Minimum-Weight Laman Graph
Higashikawa et al. [12] derived the lower bound by regularly arranging the same units each of which consists of five points. The key point of their method is that, by adding one unit, the number of points increases by 4, and at the same time, the number of edge crossings increases by 5. Thus, the lower bound is derived by the ratio \(\frac{5}{4}=1.25\). We improve the lower bound by extending the idea to arrange two types of units \(U^\text{(even)}\) and \(U^\text{(odd)}\) alternately, where each unit consists of eight points. The alternate arrangement of \(U^\text{(even)}\) and \(U^\text{(odd)}\) is illustrated in Fig. 1. Both of these two units \(U^\text{(even)}\) and \(U^\text{(odd)}\) are positioned so as to derive the isomorphic Euclidean minimum-weight Laman graphs in all units. The alternation of two different types of units instead of the same type will give two crossings between the neighboring units. Let \(t\) denote the number of units we arrange, and \(P(t)\) denote the point set when \(t\) units are arranged. Also, we denote the \(i\)-th unit by \(U_{i}\) \((0 \leq i \leq t-1)\) and the point \(p_{x}\) in unit \(U_{i}\) by \(p_{x}^{(i)}\).
 |
Fig. 1 Arranging \(U^\text{(even)}\) and \(U^\text{(odd)}\) alternately. |
First, we describe the details of units \(U^\text{(even)}\) and \(U^\text{(odd)}\), and show the Euclidean minimum-weight Laman graph on the point set of a unit \(U^\text{(even)}\). In case \(i\) is even, unit \(U_{i}\) is obtained by translating and rotating the eight points in \(U^\text{(even)}\) illustrated in Fig. 2, where six parameters \(d,\delta,\delta',\tau,\tau'\) and \(h_e\) are positive real numbers. (The translation and the rotation do not change the relative positions among the eight points in a unit.) Although point set \(U^\text{(even)}\) is not semi-generic, by moving the points in \(U^\text{(even)}\) infinitesimally, we can obtain a semi-generic point set without changing the inequalities on the weights of the edges. The infinitesimal move works on tie-breaking the edges of equal weights. Unit \(U^\text{(odd)}\) is obtained by replacing the parameter \(h_e\) in \(U^\text{(even)}\) with \(h_o=h_e+d+2\tau\). We carefully determine the parameters so that the two Euclidean minimum-weight Laman graphs on point sets \(U^\text{(even)}\) and \(U^\text{(odd)}\) become isomorphic.
 |
Fig. 2 \(\textsf{MLG}(U^\text{(even)})\). |
Lemma 5. Suppose that edge \(p_{2}p_{5}\) is infinitesimally shorter than \(p_{1}p_{6}\) and the parameters \(d,\delta,\delta',\tau,\tau'\) and \(h_e\) or \(h_o\) satisfy the following conditions:
- (A) \(\delta'>3\delta,\delta+\tau'\)
- (B) \(d>\delta+\tau,2\delta'\)
- (C) \(d+\delta+2\tau+\tau'<h_e,h_o<\frac{\delta(\delta'-3\delta)}{2\tau'},\frac{(d-\delta')^2-(\delta'-\delta)^2}{2\tau}\)
Then, the Euclidean minimum-weight Laman graph on a point set \(U^\text{(even)}\) is the geometric graph illustrated in Fig. 2, i.e., the geometric graph edge-induced by \(\{p_{0}p_{1}, p_{0}p_{2}, p_{1}p_{2}, p_{1}p_{3}, p_{1}p_{5}, p_{2}p_{3}, p_{2}p_{5}, p_{2}p_{6}, p_{4}p_{5}, p_{4}p_{6}, p_{5}p_{6}, p_{5}p_{7}, p_{6}p_{7}\}\). The Euclidean minimum-weight Laman graph on \(U^\text{(odd)}\) is the graph obtained by replacing \(h_e\) in Fig. 2 with \(h_o\).
Proof. We prove this lemma by showing that the geometric graph illustrated in Fig. 2 is a Laman graph and that all edges not illustrated in Fig. 2 are not included in \(\textsf{MLG}(U^\text{(even)})\). For discriminating whether an edge is in \(\textsf{MLG}(U^\text{(even)})\) or not, we use Lemma 2.
First, we show the weights of all edges in increasing order to compare them.
| \[\begin{aligned} \|p_{1}p_{2}\| &= \|p_{5}p_{6}\| = 2\delta \\ < \|p_{4}p_{5}\| &= \|p_{6}p_{7}\| = \sqrt{(\delta'-\delta)^2+{\tau'}^2} \\ < \|p_{4}p_{6}\| &= \|p_{5}p_{7}\| = \sqrt{(\delta'+\delta)^2+{\tau'}^2} \\ < \|p_{4}p_{7}\| &= 2\delta' \\ < \|p_{0}p_{1}\| &= \|p_{2}p_{3}\| = \sqrt{(d-\delta)^2+\tau^2} \\ < \|p_{0}p_{2}\| &= \|p_{1}p_{3}\| = \sqrt{(d+\delta)^2+\tau^2} \\ < \|p_{0}p_{3}\| &= 2d \\ < \|p_{1}p_{5}\| &= \|p_{2}p_{6}\| = h_e \\ < \|p_{2}p_{5}\| &\lessapprox \|p_{1}p_{6}\| = \sqrt{4\delta^2+{h_e}^2} \\ < \|p_{0}p_{4}\| &= \|p_{3}p_{7}\| = \sqrt{(d-\delta')^2+(h_e-\tau-\tau')^2} \\ < \|p_{0}p_{5}\| &= \|p_{3}p_{6}\| = \sqrt{(d-\delta)^2+(h_e-\tau)^2} \\ < \|p_{0}p_{6}\| &= \|p_{3}p_{5}\| = \sqrt{(d+\delta)^2+(h_e-\tau)^2} \\ < \|p_{1}p_{4}\| &= \|p_{2}p_{7}\| = \sqrt{(\delta'-\delta)^2+(h_e-\tau')^2} \\ < \|p_{1}p_{7}\| &= \|p_{2}p_{4}\| = \sqrt{(\delta'+\delta)^2+(h_e-\tau')^2} \\ < \|p_{0}p_{7}\| &= \|p_{3}p_{4}\| = \sqrt{(d+\delta')^2+(h_e-\tau-\tau')^2}, \end{aligned}\] |
where \(\|p_{2}p_{5}\| \lessapprox \|p_{1}p_{6}\| = \sqrt{4\delta^2+{h_e}^2}\) means that \(\|p_{2}p_{5}\| = \|p_{1}p_{6}\| = \sqrt{4\delta^2+{h_e}^2}\) holds if we ignore the infinitesimal move of the points and that \(\|p_{2}p_{5}\|\) is infinitesimally smaller than \(\|p_{1}p_{6}\|\) by the tie-break of the infinitesimal move.
Next, we focus on each of the edges not illustrated in Fig. 2. For a given edge \(e\) and a point set \(Q\subseteq U^\text{(even)}\), we denote \(E_{e}(Q)\) as the set of edges shorter than \(e\) in the geometric complete graph \(K(Q)\). For edge \({p_{0}}{p_{3}}\), suppose that we have a point set \(Q = \{p_{0},p_{1},p_{2},p_{3}\}\). Then, we can obtain the set \(E_{{p_{0}}{p_{3}}}(Q)\) of edges shorter than \(\|{p_{0}}{p_{3}}\|\) in \(K(Q)\) as \(E_{{p_{0}}{p_{3}}}(Q) = \{{p_{0}}{p_{1}},{p_{0}}{p_{2}},\, {p_{1}}{p_{2}},\, {p_{1}}{p_{3}},\, {p_{2}}{p_{3}}\}\). Since graph \((Q, E_{{p_{0}}{p_{3}}}(Q))\) is a Laman graph on \(Q\), \({p_{0}}{p_{3}} \notin \textsf{MLG}(U^\text{(even)})\) holds by Lemma 2. For edge \({p_{4}}{p_{7}}\), suppose \(Q = \{p_{4},p_{5},p_{6},p_{7}\}\). Then we can obtain the edge set \(E_{p_{4}p_{7}}(Q)\). By the same argument with edge \(p_{0}p_{3}\), \(p_{4}p_{7} \notin \textsf{MLG}(U^\text{(even)})\) holds.
As for the rest of edges not illustrated in Fig. 2, they are longer than edge \(p_{2}p_{5}\). Let us discuss edge \(p_{1}p_{6}\) as a representative among them, and suppose that \(Q=U^\text{(even)}\). We can obtain an edge set \(E_{{p_{1}}{p_{6}}}(Q)\). Since graph \((Q,E_{p_{1}p_{6}}(Q))\) include the Laman graph on \(Q\) illustrated in Fig. 2, \(p_{1}p_{6} \notin \textsf{MLG}(U^\text{(even)})\) holds by Lemma 2. By a similar argument, any other edge \(e\) longer than edge \(p_{2}p_{5}\) is not included in \(\textsf{MLG}(U^\text{(even)})\). As a result, we can prove the first statement on \(U^\text{(even)}\). From the argument for constructing \(U^\text{(odd)}\), we can say that the same holds for \(\textsf{MLG}(U^\text{(odd)})\).\(\tag*{◻}\)
Next, we consider the point set \(P(t)\) obtained by arranging \(t\) units. In case \(t = 1\), \(P(1)\) is \(U^\text{(even)}\) itself, and thus the graph in Fig. 2 is \(\textsf{MLG}(P(1))\). In case \(t > 1\), we alternately arrange \(U^\text{(even)}\) and \(U^\text{(odd)}\) as in Fig. 1. More precisely, for integer \(i\) \((0\leq i \leq t-1)\), \(U_{i}\) is \(U^\text{(even)}\) if \(i\) is even and \(U^\text{(odd)}\) if \(i\) is odd. We arrange \(t\) units \(U_{0}, U_{1}, \ldots, U_{t-1}\) as \(P(t)\) so that every four points \(p_{0}^{(i)},p_{1}^{(i)},p_{2}^{(i)},p_{3}^{(i)}\) of unit \(U_{i}\) lie on the same circumference \(C_0\). In addition, for all integer \(i\) \((0\leq i \leq t-2)\) two points \(p_{3}^{(i)}\) of unit \(U_{i}\) and \(p_{0}^{(i+1)}\) of unit \(U_{i+1}\) are adjusted to the same position and are regarded as the same point. The following lemma tells which edge is in \(\textsf{MLG}(P(t))\).
Lemma 6. The set of edges in \(\textsf{MLG}(P(t))\) is a union of the set of edges in \(\textsf{MLG}(U_{i})\) for \(0\leq i \leq t-1\) and the set of edges \({p_{2}^{(i)}}{p_{1}^{(i+1)}}\) between two neighboring units \(U_{i}\) and \(U_{i+1}\) for \(0\leq i \leq t-2\).
Proof. We can prove this lemma by a similar argument with Lemma 5. For edges between two points in the same unit \(U_{i}\), all edges not included in \(\textsf{MLG}(U_{i})\) are excluded from \(\textsf{MLG}(P(t))\) by the same argument. For edges between different units, only edges \({p_{2}^{(i)}}{p_{1}^{(i+1)}}\) are included in the \(E(\textsf{MLG}(P(t)))\) and no other edges are included. For all integer \(i\) \((0\leq i \leq t-1)\), the weight of edge \(\|{p_{2}^{(i)}}{p_{1}^{(i+1)}}\|\) can be approximated to \(2d\) by adjusting four parameters \(\delta,\delta',\tau,\tau'\) very small with satisfying the conditions (A) to (C) in Lemma 5. For all even \(x\), the weights of the edges \({p_{7}^{(x)}}{p_{4}^{(x+1)}}\) and \({p_{7}^{(x)}}{p_{1}^{(x+1)}}\) can be approximated to \(\sqrt{5}d\) by making \(h_e\) a small value with satisfying condition (C) in Lemma 5 (and symmetrically for edges \({p_{4}^{(x)}}{p_{7}^{(x-1)}}\) and \({p_{4}^{(x)}}{p_{3}^{(x-1)}}\)). The weights of the other edges between different units are larger than those of these edges. Note that all edges included in \(\textsf{MLG}(U_{i})\) for each unit \(U_{i}\) are shorter than either edge \({p_{7}^{(x)}}{p_{4}^{(x+1)}}\) or \({p_{7}^{(x)}}{p_{1}^{(x+1)}}\). If we consider an edge set \(E\) that is shorter than the weight \(\text{min}(\|{p_{7}^{(x)}}{p_{4}^{(x+1)}}\|, \|{p_{7}^{(x)}}{p_{1}^{(x+1)}}\|\)), then the graph \((P(t), E)\) includes a Laman graph on the point set \(P(t)\). Therefore, edges \({p_{7}^{(x)}}{p_{4}^{(x+1)}}\) and \({p_{7}^{(x)}}{p_{1}^{(x+1)}}\) are not included in \(E(\textsf{MLG}(P(t)))\) by Lemma 2. Furthermore, since all edges between different units except \({p_{2}^{(i)}}{p_{1}^{(i+1)}}\) are longer than either edge \({p_{7}^{(x)}}{p_{4}^{(x+1)}}\) or \({p_{7}^{(x)}}{p_{1}^{(x+1)}}\), they are not included in the \(E(\textsf{MLG}(P(t)))\).\(\tag*{◻}\)
Now let us count the number of edge crossings in \(\textsf{MLG}(P(t))\). For each unit \(U_{i}\) (\(0\leq i \leq t-1\)), we have eight crossings in \(\textsf{MLG}(U_{i})\). In addition, for each neighboring units \(U_{i}\) and \(U_{i+1}\) (\(0 \leq i \leq t-2\)), we have two crossings \(({p_{2}^{(i)}}{p_{1}^{(i+1)}},{p_{1}^{(i)}}{p_{3}^{(i)}})\) and \(({p_{2}^{(i)}}{p_{1}^{(i+1)}},{p_{0}^{(i+1)}}{p_{2}^{(i+1)}})\). Thus, the total number of edge crossings of \(\textsf{MLG}(P(t))\) is \(8t+2(t-1)=10t-2\). And since the number of points is \(7t+1\) in this case, we obtain the following equation:
| \[\frac{\sigma(\textsf{MLG}(P(t)))}{|P(t)|}=\frac{10t-2}{7t+1}=\frac{10}{7}-\frac{24}{49t+7}.\] |
Here, we determine the radius \(R\) of circle \(C_0\) as
| \[R=\frac{\sqrt{((d-\delta)^2+\tau^2)((d+\delta)^2+\tau^2)}}{2\tau}.\] |
By adjusting parameters \(d,\delta,\delta',\tau,\tau', h_e\) and \(h_o\) so that they are satisfying conditions (A) to (C) in Lemma5, \(h_o=h_e+d+2\tau\) and \(2\pi R \gg 2t(d+\delta)\), the number of units \(t\) can be made arbitrarily large. In other words, for any \(\epsilon > 0\), there exists a point set \(P\) such that the total number of edge crossings \(\sigma(\textsf{MLG}(P))\) is at least \((\frac{10}{7}-\epsilon)|P|\). Although the above point set \(P\) is not semi-generic, we can obtain a semi-generic point set \(P'\) such that the topology of \(\textsf{MLG}(P')\) is the same as \(\textsf{MLG}(P)\) by moving each point in \(P\) infinitesimally.
Theorem 1. For any \(\epsilon > 0\), there exists a set of semi-generic points \(P\) such that the total number of edge crossings of \(\textsf{MLG}(P)\) is greater than \((\frac{10}{7}-\epsilon)|P|\).
Now, we focus on the maximum geometric thickness of \(\textsf{MLG}(P)\). The graph shown in Fig. 3 is the edge-crossing graph of \(\textsf{MLG}(U^\text{(even)})\). Vertex \({p_{i}p_{j}}\) in Fig. 3 corresponds to edge \({p_{i}p_{j}}\) in \(\textsf{MLG}(U^\text{(even)})\), and edge (\({p_{i_1}p_{j_1}}, {p_{i_2}p_{j_2}})\) corresponds to an edge crossing of edges \({p_{i_1}p_{j_1}}\) and \({p_{i_2}p_{j_2}}\) in \(\textsf{MLG}(U^\text{(even)})\). This graph contains a cycle of length 5. Hence, this graph is not 2-colorable. In other words, its chromatic number is 3 or more. Since the geometric thickness of a geometric graph is equal to the chromatic number of its edge-crossing graph from Lemma 4, the geometric thickness of MLG of \(U^\text{(even)}\) is 3 or more. Thus, we have the following theorem.
 |
Fig. 3 edge-crossing graph of \(\textsf{MLG}(U^\text{(even)})\). |
Theorem 2. There exists a set of semi-generic points \(P\) such that the geometric thickness of \(\textsf{MLG}(P)\) is greater than or equal to 3.
3.2 Minimum-Weight (2,2)-Tight Graph
In Sect. 3.1, we alternately arranged two types of units \(U^\text{(even)}\) and \(U^\text{(odd)}\). In this subsection, we derive a lower bound for the maximum total number of edge crossings of Euclidean minimum-weight \((2,2)\text{-tight graph}\) by a new approach: While we arrange mutually different \(t\) units, the position of the points in the units is designed so that the Euclidean minimum-weight \((2,2)\text{-tight graph}\)s on all units are isomorphic as shown in Fig. 4. As in Sect. 3.1, we first describe each unit \(U_{i}\) and the rules for arranging \(t\) units. Let \(P(t)\) denote the point set with \(t\) units. Although point set \(P(t)\) is not semi-generic, by moving the points in \(P(t)\) infinitesimally, we can obtain a semi-generic point set without changing the inequalities on the weights of the edges. Then we discuss the Euclidean minimum-weight \((2,2)\text{-tight graph}\) on the point set with \(t\) units, and finally the total number of edge crossings of the \((2,2)\textsf{-MTG}(P(t))\).
 |
Fig. 4 Minimum-weight \((2,2)\text{-tight graph}\) on a point set arranging \(t\) units. |
For each \(i\) in \(0 \leq i \leq t - 1\), unit \(U_{i}\) consists of six points. The relative position of the points in each unit is illustrated in Fig. 5, and is determined by three parameters \(\delta,\epsilon\) and \(d_i\). Two parameters \(\delta,\epsilon\) are common for all units, and parameter \(d_i\) is different in each unit. In each \(U_{i}\), three points \(p_{0}^{(i)}\), \(p_{3}^{(i)}\) and \(p_{4}^{(i)}\) (respectively, \(p_{1}^{(i)}\), \(p_{2}^{(i)}\) and \(p_{5}^{(i)}\)) have the same \(x\)-coordinate. The height of \(U_{i}\) is always \(\epsilon\). On the other hand, as \(i\) increases, the width of \(U_{i}\) also increases.
 |
Fig. 5 \((2,2)\textsf{-MTG}(U_{i})\). |
Lemma 7. Suppose that the parameters \(d_i,\delta\) and \(\epsilon\) satisfy the following conditions:
- \(\delta < d_i\)
- \(\epsilon < d_i - \delta\)
Then, the Euclidean minimum-weight (2,2)-tight Graph on point set \(U_{i}\) is the geometric graph illustrated in Fig. 5, i.e., the geometric graph induced by \(E_{\text{MTG}}^{(i)} = \{p_{0}^{(i)}p_{1}^{(i)}, p_{0}^{(i)}p_{2}^{(i)}, p_{1}^{(i)}p_{2}^{(i)}, p_{1}^{(i)}p_{3}^{(i)}, p_{1}^{(i)}p_{4}^{(i)}, p_{2}^{(i)}p_{3}^{(i)}, p_{2}^{(i)}p_{4}^{(i)}, p_{3}^{(i)}p_{4}^{(i)}, p_{3}^{(i)}p_{5}^{(i)}, p_{4}^{(i)}p_{5}^{(i)}\}\).
Proof. We can confirm that the geometric graph \((U_{i},E_{\text{MTG}}^{(i)})\) illustrated in Fig. 5 satisfies the definition of a \((2,2)\text{-tight graph}\). Then, we prove this lemma by showing that all edges in \(K(U_{i}) \setminus E_{\text{MTG}}^{(i)}\) (i.e., the edges not illustrated in Fig. 5) are not included in \((2,2)\textsf{-MTG}(U_{i})\), where \(K(U_{i})\) is the geometric complete graph on \(U_{i}\). For discriminating whether an edge is in \((2,2)\textsf{-MTG}(U_{i})\) or not, we use Lemma 3.
First, we show the weights of all edges in increasing order to compare them. In this proof, for convenience, we use \(p_{j}\) to denote \(p_{j}^{(i)}\).
| \[\begin{aligned} \|p_{1}p_{2}\| &= \|p_{3}p_{4}\| = \delta \\ < \|p_{0}p_{1}\| &= \|p_{2}p_{3}\| = \|p_{4}p_{5}\| = \sqrt{{d_i}^2+\epsilon^2} \\ < \|p_{0}p_{2}\| &= \|p_{1}p_{3}\| = \|p_{2}p_{4}\| \\ &= \|p_{3}p_{5}\| = \sqrt{{(d_i+\delta)}^2+\epsilon^2} \\ < \|p_{1}p_{4}\| &= \sqrt{(2\delta+d_i)^2+\epsilon^2} \\ < \|p_{0}p_{3}\| &= \|p_{2}p_{5}\| = 2d_i + \delta \\ < \|p_{0}p_{4}\| &= \|p_{1}p_{5}\| = 2d_i + 2\delta \\ < \|p_{0}p_{5}\| &= \sqrt{(3d_i+2\delta)^2+\epsilon^2} \end{aligned}\] |
We focus on edge \(p_{0}p_{3} \in K(U_{i}) \setminus E_{\text{MTG}}^{(i)}\). Among the edges in \(K(U_{i})\), we can obtain the set \(E_{p_{0}p_{3}}(U_{i})\) of edges shorter than \(\|{p_{0}}{p_{3}}\|\) as \(E_{p_{0}p_{3}}(U_{i}) = \{p_{0}p_{1}, p_{0}p_{2}, p_{1}p_{2}, p_{1}p_{3}, p_{1}p_{4}, p_{2}p_{3}, p_{2}p_{4}, p_{3}p_{4}, p_{3}p_{5}, p_{4}p_{5} \}\). We can confirm the geometric graph \((U_{i}, E_{p_{0}p_{3}}(U_{i}))\) satisfies the definition of a \((2,2)\text{-tight graph}\) on \(U_{i}\). By Lemma 3, we have \({p_{0}}{p_{3}} \notin E((2,2)\textsf{-MTG}(U_{i}))\).
Any other edge \(p_{x}p_{y} \in K(U_{i}) \setminus E_{\text{MTG}}^{(i)}\) is longer than edge \(p_{0}p_{3}\). Thus, \(E_{p_{0}p_{3}}(U_{i})\) is a subset of \(E_{p_{x}p_{y}}(U_{i})\), where \(E_{p_{x}p_{y}}(U_{i})\) is the set of edges shorter than \(\|p_{x}p_{y}\|\). Since \((U_{i}, E_{p_{0}p_{3}}(U_{i}))\) is a \((2,2)\text{-tight graph}\) as stated above, we have \(p_{x}p_{y} \notin E((2,2)\textsf{-MTG}(U_{i}))\) by Lemma 3.\(\tag*{◻}\)
As illustrated in Fig. 4, we vertically arrange \(t\) units so that two points \(p_{3}^{(i)}\) and \(p_{1}^{(i+1)}\) (respectively, \(p_{4}^{(i)}\) and \(p_{2}^{(i+1)}\)) in each of the neighboring units \(U_{i},U_{i+1}\) have the same \(y\)-coordinate. The lengths \(\|p_{3}^{(i)} p_{1}^{(i+1)}\|\) and \(\|p_{4}^{(i)} p_{2}^{(i+1)}\|\) is fixed to \(h\) for all \(i\)’s.
Lemma 8. Suppose that the parameters \(d_i,\delta,\epsilon\) and \(h\) satisfy the following conditions:
- \(d_{i+1} > 2d_{i} + \delta\)
- \(\delta < d_0\)
- \(h > 2d_{t-1} + \delta\)
- \(\epsilon < \frac{(d_{1}-d_{0}-\delta)^2}{4h}, \frac{(d_{1}-2d_{0}-\delta)}{2h}\)
The set of edges in \((2,2)\textsf{-MTG}(P(t))\) is a union of \(E_{\text{MTG}}^{(i)}\) for \(0\leq i \leq t-1\) and the set of edges \({p_{3}^{(i)}}{p_{1}^{(i+1)}}\) and \({p_{4}^{(i)}}{p_{2}^{(i+1)}}\) between two neighboring units \(U_{i}\) and \(U_{i+1}\) for \(0\leq i \leq t-2\), where \(E_{\text{MTG}}^{(i)}\) is the set of edges in \((2,2)\textsf{-MTG}(U_{i})\).
Proof. We can prove this lemma by a similar argument with Lemma 7. For discriminating whether an edge is in \((2,2)\textsf{-MTG}(P(t))\) or not, we use Lemma 3. As for the edges in a unit, by the same argument, we can exclude all edges in \(K(U_{i}) \setminus E_{\text{MTG}}^{(i)}\) for all \(i\)’s. In other words, the edges not illustrated in Fig. 5 are excluded.
Now, we discriminate the set \(E_\text{dif}\) of edges between two different units, where \(E_\text{dif} = \{ p_{x}^{(i)}p_{y}^{(j)} \mid 0 \leq x,y \leq 5,\ 0\leq i < j \leq t-1 \}\). Let \(E_\text{in}\) be a set of edges in \(E_\text{dif}\) that are illustrated in Fig. 4, i.e., \(E_\text{in} = \{p_{3}^{(i)}p_{1}^{(i+1)}, p_{4}^{(i)}p_{2}^{(i+1)} \mid 0\leq i \leq t-2\}\). We focus on edge \(e_\text{ex} \in E_\text{dif} \setminus E_\text{in}\) (i.e., the edges not illustrated in Fig. 4), and show that \(e_\text{ex}\) is not an edge of \((2,2)\textsf{-MTG}(P(t))\) by comparing \(e_\text{ex}\) with the edges in \(E_\text{in}\) and \(E_{\text{MTG}}^{(i)}\). By conditions (I) to (IV) in this lemma, we can confirm that \(\forall e_\text{in} \in E_\text{in}, e_\text{ex} \in E_\text{dif} \setminus E_\text{in}: \|e_\text{in}\| < \|e_\text{ex}\|\) holds. By condition (III) in this lemma, \(\forall e_\text{MTG} \in E_{\text{MTG}}^{(i)}, e_\text{in} \in E_\text{in}: \|e_\text{MTG}\| < \|e_\text{in}\|\) holds for \(0 \leq i \leq t-1\). Thus, we have \(\forall e_\text{MTG} \in E_{\text{MTG}}^{(i)}, e_\text{ex} \in E_\text{dif} \setminus {E_\text{in}}: \|e_\text{MTG}\| < \|e_\text{ex}\|\). From above two inequalities on \(e_\text{ex}\), for all \(e_\text{ex} \in E_\text{dif} \setminus E_\text{in}\) we have \(E_\text{in} \subseteq E_{e_\text{ex}}(P(t))\) and \(E_{\text{MTG}}^{(i)} \subseteq E_{e_\text{ex}}(P(t))\) for \(0 \leq i \leq t-1\), where \(E_{e_\text{ex}}(P(t))\) is the set of edges shorter than \(\|e_\text{ex}\|\). This means that \((\bigcup_{i}{E_{\text{MTG}}^{(i)}}) \cup E_\text{in}\) is a subset of \(E_{e_\text{ex}}(P(t))\). We can confirm that the geometric graph induced by \((\bigcup_{i}{E_{\text{MTG}}^{(i)}}) \cup E_\text{in}\) satisfies the definition of a \((2,2)\text{-tight graph}\). By Lemma 3, we have \(e_\text{ex} \notin E((2,2)\textsf{-MTG}(P(t)))\) for all \(e_\text{ex} \in E_\text{dif} \setminus E_\text{in}\).\(\tag*{◻}\)
Since there are five edge crossings in each unit \(U_{i}\) \((0\leq i \leq t-1)\) and six edge crossings for each neighboring \(U_{i}\) and \(U_{i+1}\) \((0\leq i \leq t-2)\), the total number of edge crossings of \((2,2)\textsf{-MTG}(P(t))\) is \(5t+6(t-1)=11t-6\). Since the number of points is \(6t\) in this case, we obtain the following equation:
| \[\frac{\sigma((2,2)\textsf{-MTG}(P(t)))}{|P(t)|}=\frac{11t-6}{6t}=\frac{11}{6}-\frac{1}{t}.\] |
Thus, with a sufficiently large \(t\), for any \(\epsilon > 0\), there exists a point set \(P\) such that the total number of edge crossings \(\sigma((2,2)\textsf{-MTG}(P))\) is at least \((\frac{11}{6}-\epsilon)|P|\). Although the above point set \(P\) is not semi-generic, as in the previous subsection, we can obtain a semi-generic point set \(P'\) such that the topology of \((2,2)\textsf{-MTG}(P')\) is the same as \((2,2)\textsf{-MTG}(P)\) by moving each point in \(P\) infinitesimally.
Theorem 3. For any \(\epsilon > 0\), there exists a set of semi-generic points \(P\) such that the total number of edge crossings of \((2,2)\textsf{-MTG}(P)\) is greater than \((\frac{11}{6}-\epsilon)|P|\).
In the following, we discuss the thickness. We consider a point set \(P_8 \subseteq P(2)\) consisting of eight points \(p_{2}^{(0)}, p_{3}^{(0)}, p_{4}^{(0)}, p_{5}^{(0)}, p_{0}^{(1)}, p_{1}^{(1)}, p_{2}^{(1)}\), and \(p_{3}^{(1)}\). \((2,2)\textsf{-MTG}(P_8)\) is the geometric graph illustrated in Fig. 6, i.e., the graph induced by \(\{p_{2}^{(0)}p_{3}^{(0)}, p_{2}^{(0)}p_{4}^{(0)}, p_{2}^{(0)}p_{5}^{(0)}, p_{3}^{(0)}p_{4}^{(0)}, p_{3}^{(0)}p_{5}^{(0)}, p_{4}^{(0)}p_{5}^{(0)}, p_{3}^{(0)}p_{1}^{(1)}, p_{4}^{(0)}p_{2}^{(1)}, p_{0}^{(1)}p_{1}^{(1)}, p_{0}^{(1)}p_{2}^{(1)}, p_{0}^{(1)}p_{3}^{(1)}, p_{1}^{(1)}p_{2}^{(1)}, p_{1}^{(1)}p_{3}^{(1)}, p_{2}^{(1)}p_{3}^{(1)}\}\). We can prove it by a similar argument as in the proof of Lemma 8. The graph shown in Fig. 7 is the edge-crossing graph of \((2,2)\textsf{-MTG}(P_8)\). This graph contains a cycle of length 5. Therefore, with the same reason as in the case of \(\textsf{MLG}(P)\) and Lemma 4, the geometric thickness of \((2,2)\textsf{-MTG}(P_8)\) is at least 3. Thus, we have the following theorem.
 |
Fig. 6 \((2,2)\textsf{-MTG}(P_8)\). |
 |
Fig. 7 Edge-crossing graph of \((2,2)\textsf{-MTG}(P_8)\). |
Theorem 4. There exists a set of semi-generic points \(P\) such that the geometric thickness of \((2,2)\textsf{-MTG}(P)\) is greater than or equal to 3.
4. Concluding Remarks
As for the maximum total number of edge crossings, with the idea of regularly arranging different units, we improved the lower bound for Euclidean minimum-weight Laman graphs and newly derived the lower bound for Euclidean minimum-weight \((2,2)\text{-tight graph}\)s. As for the maximum geometric thickness, we showed that the lower bounds for Euclidean minimum-weight Laman and \((2,2)\text{-tight graph}\)s are 3 since we have a cycle of length 5 in each of their edge-crossing graphs.
A gap, however, still exists between the upper and lower bounds for the maximum total number of edge crossings of \(\textsf{MLG}(P)\) for a semi-generic point set \(P\). One of the challenges is to fill this gap. In our view, our technique has potential for further improvement by applying other units. There is also a large gap for \((2,2)\textsf{-MTG}(P)\). The reason for this large gap is due to the difficulty that the technique for the upper bound of \(\textsf{MLG}(P)\) cannot be directly applied to \((2,2)\textsf{-MTG}(P)\) since it may contain cliques of size 4. Bereg et al. [11] showed 6-planarity of \(\textsf{MLG}(P)\). However, it does not hold in \((2,2)\textsf{-MTG}(P)\). In fact, there exists a point set \(P\) such that an edge crosses other seven edges in \((2,2)\textsf{-MTG}(P)\). In the point set \(P\) shown in Fig. 8, the parameters \(d,\delta,\epsilon\), and \(h\) are defined to satisfy the conditions in Lemma 8. We can confirm that edge \(p_{1}p_{4}\) crosses seven other edges. Thus, new techniques are necessary to address the upper bound of the maximum total number of edge crossings of \((2,2)\text{-tight graph}\) (and also for general \((k,\ell)\text{-tight graph}\)). For the lower bound, we believe that our technique of arranging different units made under the same design is promising for general \(k\) and \(\ell\).
 |
Fig. 8 Edge \(p_{1}p_{4}\) crosses 7 other edges in \((2,2)\textsf{-MTG}(P)\). |
A gap also exists for the maximum geometric thickness of \(\textsf{MLG}(P)\). Higashikawa et al. [12] gave a suggestion for improving the upper bound. A planar triangle-free graph is 3-colorable, and the edge-crossing graph of \(\textsf{MLG}(P)\) is triangle-free for any semi-generic point set \(P\). Thus, if we prove the planarity of the edge-crossing graphs, the upper bound becomes 3 (i.e., we have the matching upper and lower bounds). As for the maximum geometric thickness for \((2,2)\textsf{-MTG}(P)\), the upper bound is open. Moreover, it is not known whether the edge-crossing graph of \((2,2)\textsf{-MTG}(P)\) is triangle-free or not.
Acknowledgments
This research was partially supported by JSPS KAKENHI Grant Numbers 20H05964, 22H03549, 22H00513, 23K17158, 23H03349, and 23H03350.
References
[1] J.E. Graver, B. Servatius, and H. Servatius, “Combinatorial rigidity,” pp.12-65, American Mathematical Soc., 1993.
CrossRef
[2] G. Laman, “On graphs and rigidity of plane skeletal structures,” Journal of Engineering Mathematics, vol.4, no.4, pp.331-340, 1970.
CrossRef
[3] B. Servatius, “The geometry of frameworks: Rigidity, mechanisms and cad,” MAA Notes, pp.81-87, 2000.
[4] M.F. Thorpe and P.M. Duxbury, Rigidity theory and applications, Springer Science & Business Media, 1999.
[5] A. Lee and I. Streinu, “Pebble game algorithms and sparse graphs,” Discrete Mathematics, vol.308, no.8, pp.1425-1437, 2008.
CrossRef
[6] C.S.J.A. Nash-Williams, “Edge-Disjoint Spanning Trees of Finite Graphs,” Journal of the London Mathematical Society, vol.s1-36, no.1, pp.445-450, 1961.
CrossRef
[7] W.T. Tutte, “On the Problem of Decomposing a Graph into n Connected Factors,” Journal of the London Mathematical Society, vol.s1-36, no.1, pp.221-230, 1961.
CrossRef
[8] N. Katoh and S. Tanigawa, “A proof of the molecular conjecture,” Discrete & Computational Geometry, vol.45, no.4, pp.647-700, 2011.
[9] A. Nixon, J.C. Owen, and S.C. Power, “Rigidity of frameworks supported on surfaces,” SIAM Journal on Discrete Mathematics, vol.26, no.4, pp.1733-1757, 2012.
CrossRef
[10] P.C. Kainen, “Thickness and coarseness of graphs,” Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol.39, no.1, pp.88-95, 1973.
CrossRef
[11] S. Bereg, S.-H. Hong, N. Katoh, S.-H. Poon, and S.-I. Tanigawa, “On the edge crossing properties of Euclidean minimum weight Laman graphs,” Comput. Geom., vol.51, pp.15-24, 2016.
CrossRef
[12] Y. Higashikawa, N. Katoh, and Y. Kobayashi, “Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs,” International Journal of Computer Mathematics: Computer Systems Theory, vol.8, no.1, pp.67-79, 2023.
CrossRef
[13] P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristán, and M. Saumell, “Some properties of k-Delaunay and k-Gabriel graphs,” Comput. Geom., vol.46, no.2, pp.131-139, 2013.
CrossRef
[14] M. Lorea, “On matroidal families,” Discrete Mathematics, vol.28, no.1, pp.103-106, 1979.
CrossRef
Authors
Hokkaido University
received the B.Eng. degree from Hokkaido University, Sapporo, Japan, in 2022. He is currently a master student at graduate school of information science and technology, Hokkaido University. His current research interests include computational geometry.
 |
Hokkaido University
received the B.Eng. degree from Hokkaido University, Sapporo, Japan, in 2022. He is currently a master student at graduate school of information science and technology, Hokkaido University. His current research interests include combinatorics on strings.
 |
Hokkaido University
received the B.Eng., M.Info., and Ph.D. degrees in Informatics from Kyoto University in 2008, 2010, and 2013, respectively. He is now an associate professor at Hokkaido University. His research interests include satisfiability problems and circuit complexity.
 |
Hokkaido University
received the B.E. and M.E. degrees in information science and Ph.D. in informatics from Kyoto University, Kyoto, Japan in 1995, 1997 and 2004, respectively. He was a research associate at Nara Institute of Science and Technology from 1999, a research associate at Kyoto University from 2002, and an associate professor at Saitama University from 2007. Since 2019, he is a professor at Hokkaido University. His current interests include computational geometry and algorithm design.
 |
Osaka Metropolitan University
is a researcher of computational design born in Aichi, Japan. He has studied architectural design with Prof. S. Takamatsu and theoretical computer science with Prof. N. Katoh at Kyoto University. He was awarded Young CAADRIA Award 2014. He has worked as an assistant professor at Tokyo Institute of Technology since 2015. Currently he is a lecturer at Osaka Metropolitan University.
 |
University of Hyogo
is an associate professor in Graduate School of Information Science at University of Hyogo. He was an assistant professor in Faculty of Science and Engineering at Chuo University from 2015 to 2018, and also a JSPS Research Fellowship for Young Scientists (PD) at Kyoto University from 2014 to 2015. He received the B. Eng, M. Eng. and Dr. Eng. degrees from Kyoto University in 2008,2010 and 2014, respectively. His interest is on design and analysis of algorithms, combinatorial optimization, discrete mathematics, computational geometry, and operations research. He is a member of IPSJ and OR Soc. Japan.
 |
University of Hyogo
received the B.Eng., M.Eng. and Dr.Eng. degrees in Applied Mathematics and Physics from Kyoto University in 1973, 1975 and 1981, respectively. He was a Assistant Professor during 1981-1982, an Associate Professor during 1982-1990, and a Professor during 1990-1997, respectively, at Department of Management Science of Kobe University of Commerce. And also he was a Professor during 1997-2015, 2015-2019, and 2019-, at Department of Architecture and Architectural Systems of Kyoto University, Graduate School of Science and Technology of Kwansei Gakuin University, and School of Social Information Science of University of Hyogo, respectively. Currently he is a Professor in Graduate School of Information Science at University of Hyogo. He was rewarded Hao Wang Award in 2000. His research interests include the design and analysis of combinatorial and geometric algorithms, data mining and architectural information systems.
 |
