1-1hit |
Yuki KAWAKAMI Shun TAKAHASHI Kazuhisa SETO Takashi HORIYAMA Yuki KOBAYASHI Yuya HIGASHIKAWA Naoki KATOH
We explore the maximum total number of edge crossings and the maximum geometric thickness of the Euclidean minimum-weight (k, ℓ)-tight graph on a planar point set P. In this paper, we show that (10/7-ε)|P| and (11/6-ε)|P| are lower bounds for the maximum total number of edge crossings for any ε > 0 in cases (k,ℓ)=(2,3) and (2,2), respectively. We also show that the lower bound for the maximum geometric thickness is 3 for both cases. In the proofs, we apply the method of arranging isomorphic units regularly. While the method is developed for the proof in case (k,ℓ)=(2,3), it also works for different ℓ.