最小ラーマングラフの総交差数への新たな上下界
New Upper and Lower Bounds for the Total Number of Edge Crossings ofEuclidean Minimum Weight Laman Graphs○小林 祐貴*1，東川 雄哉*2，加藤 直樹*3，吉山 大雅*4
Yuki KOBAYASHI＊1, Yuya HIGASHIKAWA＊2, Naoki KATOH＊3, and Taiga YOSHIYAMA*4*1 大阪市立大学大学院工学研究科講師

博士(工学)

Lecturer, Graduate School of Engineering, Osaka City University, Ph.D.
*2 兵庫県立大学大学院情報科学研究科准教授

博士(工学)

Associate Professor, Graduate School of Information Science, University of Hyogo, Ph.D.
*3 兵庫県立大学大学院情報科学研究科教授

博士(工学)

Professor, Graduate School of Information Science, University of Hyogo, Ph.D.
*4 大阪市立大学大学院工学研究科

前期博士課程Graduate student, Graduate School of Engineering, Osaka City University.
キーワード: デザイン科学; 計算幾何; 組合せ剛性理論; Bar-joint フレームワーク;幾何的グラフ

Keywords: Design science; Computational geometry; Combinatorial rigidity; Bar-joint frameworks; Geometric graphs.

1.

はじめにグラフ! = ($, & )について，|&| = 2|$| − 3かつ，! の任意の部分グラフ , について|& (,)| ≤ 2|$(,)| − 3が成り立で交差を減らすことも考えられる．このような目的から，本研究では 01!(/)の辺交差数の新たな上下界を明らかにする．

つとき，! をラーマングラフと呼ぶ．ラーマングラフは一

これまでに計算機実験によって 01!(/)の交差数は 2

般的な配置の bar-joint フレームワークとして平面に実現

章で示す Bereg ら 4)が示した上界よりも，かなり少ないしたとき，極小剛となる性質を持つ 1,2)．極小剛な bar-joint

ことがわかった 5)．このことから，より精緻に01!(/)のフレームワークは，少ない部材数で剛な構造物を構築す性質を調べることを試みた．なお，3 章，4 章の補題と定ることができるため，筆者らは建築への応用を目指し，理の証明は，国際会議 COCOON 2021 において発表を予

これまで研究を行なっている 3)．

定している．

ここで，本研究で対象とするグラフを定義する．平面上に.個の点集合/が与えられたとき，/の幾何的グラフは，各辺が/の 2 点間の線分の集合&により! (/) = (/, &)2. 準備
はじめに，いくつかの表記法を定義する．2を中心とすと表される．本研究において，/のどの 3 点も一直線上にる半径3の閉円板を4! (3)とし，2を中心とする半径3の円はなく，全ての頂点間の距離は異なるものとする．このを 5! (3) と す る ． こ こ で 平 面 上 の 2 点 2, 6 に つ い て ，ような仮定を満たす頂点集合を準一般的な配置と呼ぶ．

17.8(26) = 4! (26) ∩ 4" (26)とする． :;87<= (26)は線分 26

2 次元 bar-joint フレームワークを幾何的グラフと見なし，の 垂 直 二 等 分 線 と す る ． >2_17.8(26) は 17.8(26) を幾何的グラフの基礎グラフがラーマングラフであるとき， :;87<=(26)で二分して得られる閉領域のうち2を含むものユークリッドラーマングラフと呼ぶ．さらに，/についてとし，1@A_17.8(26)は17.8(26)を:;87<=(26)で二分して得のユークリッドラーマングラフを考えたとき，辺の長さられる閉領域のうち 6 を含むものとする． 1_17.8(26)はの総和が最小となるユークリッドラーマングラフ

17.8(26)を26で二分して得られる閉領域のうち，6 → 2の（Euclidean minimum weight Laman graph）を01!(/)と左側のもの，C_17.8(26)は17.8(26)を26で二分して得らする．

れる閉領域のうち，6 → 2の右側のものとする．点2と2を2 次元 bar-joint フレームワークを作成する際には，部端点とする 2 つの半直線D, D# について，D, D# のなす角の小材同士が交差することはできるだけ少なくしたい．

さ い 方 を E.FD7! (D, D# ) と し ， D, D# に 挟 ま れ る 領 域 を01!(/)がどの程度交差するか，あらかじめわかっていれ

5@.7! (D, D# )とする．

ば，接合部に厚みを持たせるなどの工夫をすることで作成したり，交差する部分については，辺長は最小ではな

最 小 全 域 木 0GH(/) と 01!(/) に つ い て 次 の 補 題 がBereg ら 4)によって示されている．

くなるが，極小剛性は有するように辺を取り替えること
日本建築学会情報システム技術委員会
第 44 回情報･システム･利用･技術シンポジウム論文集， 559-562 ， 2021 年 12 月，京都
Proceedings of the 44th Symposium on Computer Technology of Information ，Systems and Applications ， AIJ ， 559-562 ， Dec. ， 2021 ， Kyoto－ 559 －

補題 1.4) 0GH(/) ⊆ 01!(/)が成り立つ．

補題 3.4) 4 点E, :, <, K ∈ /について，線分<Kが線分E:の lens-crossing 辺であり，<Kは>2_17.8(26)のみを通過するとす
次章では補題 1 より，01!(/)の辺を0GH(/)とそれ以る．このとき，E ∈ 17.8(<K)となる．

外に分類する．
次の補題は E: ∈ 01!(/)について 17.8(E:)に含まれる/の点が満たす性質を示している．

補題 4.4) 辺 E: ∈ 01!(/) について考える．このとき，01!(/)に含まれる辺は下記となる．
>2_17.8(E:)のみを通過するE:の lens-crossing 辺(i)
補題 2.4) 辺E: ∈ 01!(/)について考える．この時，下記がは高々1 辺．
(ii)成り立つ．

1_17.8(E:) と C_17.8(E:) にそれぞれ含まれる /(i)(ii)

辺は高々1 辺．
(iii)の点は高々1 点存在する．

1_17.8(E:) と C_17.8(E:) に / の点が存在すると

1@A_17.8(E:)のみを通過する E: の lens-crossing>2_17.8(E:) と 1@A_17.8(E:) の両方を通過する
E:の lens-crossing 辺は存在しない．

き，すなわち，< ∈ 1_17.8(E:)，K ∈ 1_17.8(E:)を満たすならば，E: < <Kかつ<K ∉ 01!(/)．

acadbbc(a)ad

図 2 補題 4(iii)の状況
図 2 に補題 4(iii)の状況を示す．補題 4 より，01!(/)

dはE: ∈ 01!(/)について高々2 個の lens-crossing 辺を含むこととなる．

c

また，E: ∈ 01!(/)の fan-crossing 辺について，次の補題がある．

b
補 題 5.4) 辺 E: ∈ 01!(/) に つ い て 考 え る ． こ の と き(b)01!(/)に含まれるE:の fan-crossing 辺は高々4 本である．

図１(a) E:に対する lens-crossing 辺<K (b) E:に対する
fan-crossing 辺<K

本研究では，この補題の証明 4)をもとに，次章の補題10 と 11 を示した．

ここで，既往研究 4)と本研究において重要な分類を次のように定義する（図 1）．

ここで，01!(/)の交差数をN(/)とする．補題 4 と 5 より，01!(/)の各辺は高々6 個の交点を持つこととなる．
したがってN(/)は高々6 × (2. − 3)/2となり，下記の定理

定義 1. (lens-crossing 辺) 4 点E, :, <, K ∈ /について，線分が成り立つ．

E:と<Kが交差しており，<, K ∉ 17.8(E:)とする．このとき，<KをE:の lens-crossing 辺と呼ぶ．
定義 2. (fan-crossing 辺) 4 点E, :, <, K ∈ /について，線分E:と<Kが交差しており，<, K ∉ 17.8(E:)とする．このとき，<KをE:の fan-crossing 辺と呼ぶ．
次の 2 つの補題はE: ∈ 01!(/)の lens-crossing 辺にお図 3 |/| − 3個の交点を持つ01!(/)（赤点が交点）ける性質を示している．

報告 H109－ 560 －定理 1.4) 任意の準一般的配置の頂点集合 / について，N(/) ≤ 6|/| − 9が成り立つ．

ここで，01!(/)の交点を以下の 2 つに場合分けするた
め，次のように定義する．

Bereg らは図 3 に示すような交差数が|/| − 3となる頂

定義 3. (f-f 交点，f-l 交点) 4 点E, :, <, K ∈ /について，２線点集合 / を示しており，このことから次の定理が成り立

分E:と<Kが交差しているとする．

つ．

(i)

<KがE:の fan-crossing 辺であり，E:が cd の fancrossing 辺であるとき，E:と<Kの交点を f-f 交点

定理 2.4) N(/) ≥ |/| − 3となる準一般的配置の頂点集合/と呼ぶ．
(ii)が存在する．

cd がE:の fan-crossing 辺であり，E:が<Kの lenscrossing 辺であるとき，E:と<Kの交点を f-l 交点

さらに次の 2 つの補題を導入する．と呼ぶ．
bisect(ad)da

補題 6.6) 3 点E, :, < ∈ / が，E.FD7$ (D, D# ) < 60°かつ:, < ∈la

5@.7$ (D, D# )を満たすとする．このとき，E:と:<のうち長い辺は0GH(/)に含まれない．

clb

補 題 7.4) 4 点 E, :, <, K ∈ / が ， E.FD7$ (D, D# ) < 60° か つ60°

l’a60°l’b:, <, K ∈ 5@.7$ (D, D# )を満たすとする．このとき，E:, E<, EKd'bのうち最長の辺は0GH(/)に含まれない．

bisect(ad’)

3. U(V)の上界の改善(a)

本研究では，定理 1 で示したN(/)の上界を改善した．
WWWWWW(/) = 01!(/) ∖ 0GH(/)とする．初めに次以下では，0GH

abisect(ac’)の補題を示した．

bisect(ah’)
hh'
補題 8. E, : ∈ 0GH(/)について，fan-crossing 辺は存在しない．

pc

さらに，次の補題を示した（図 4 に補題 9 の状況を示

c'dqbす）．
補題 9. 4 点E, :, <, K ∈ /について，<Kは ab の lens-crossing(b)辺であるとする．このとき，ab は<Kの fan-crossing 辺で

図 5 (a) /の点が17.8(E:)に 1 つの場合 (b) 2 つの場合ある．
交点数を数え上げるために，次の 2 つの補題を示した．

caWWWWWW(/)について考える．E:と01!(/)に補題 10. 辺E: ∈ 0GHd

含まれるE:の fan-crossing 辺の交点には，高々2 個の f-l交点が存在する．
補題 10 は/の点が17.8(E:)に 1 つあるとき，2 つあるbときに場合分けすることで示すことができる（図 5）．
次の補題 11 は補題 10 と同様に 2 つの場合に分けて示すことができる．

図 4 cd が>2_17.8(E:)を通過して1@A_17.8(E:)は通過しない場合

報告 H109

WWWWWW(/)について，高々1 個の fan-crossing
補題 11. 辺E: ∈ 0GH
辺が0GH(/)に含まれる．

－ 561 －これらの補題を用いて，次の定理を示すことができる．

路がないといった性質を示すことができれば，さらに上界を改善できる可能性がある．現在，Rhinoceros を用い定 理 3. 準 一 般 的 配 置 の 点 集 合 / に つ い て ， N(/) ≤てインタラクティブに 01! (/)を描画できる環境を構築

2.5|/| − 5が成り立つ．

し，検討している（図 7）．

4. U(V)の下界の改善
本研究では，Bereg らが示した01!(/)の交点数よりも，より交点数の多い点集合 P の構築方法を明らかにした．

cbr

図 7 操作画面
da2r［参考文献］

1） J. Graver, B. Servatius, and H. Servatius. Combinatorial

Rigidity. Graduate Studies in Mathematics, vol. 2.
American Mathematical Society, 1993.
2） G. Laman. On graphs and rigidity of plane skeletaleRstructures. Journal of Engineering Mathematics, vol.

o4:331‒340, 1970.
3） 小林祐貴,加藤直樹,極小剛な空間充填立体bar-jointフレ(a)

a1

b1

c1

d1= a2ームワークの生成手法及び建築形態デザインへの応用,日本建築学会環境系論文集,vol. 83(745):323–331, 2018.

b2c2d24） S. Bereg, S. -H. Hong, N. Katoh, S. -H. Poon, and S.

Tanigawa. On the edge crossing properties of Euclidean
minimum

weightLamangraphs.

Computational

Geometry:Theory and Applications, vol. 51:15-24, 2016.
e1e2(b)

図 6 (a) 5 点の組を(o,R,r) (b) (o,R,r)を連結したもの

5） 吉山大雅，小林祐貴,東川雄哉，加藤直樹,最小重みLamanグラフの交差数の検証，日本建築学会大会学術講演梗概集（東海），pp.39-40,2021.
6） A. C. Yao. On constructing minimum spanning trees in k-dimensional space and related Problems. SIAM Journal
図 6(a)に示すような 5 点{E, :, <, K, 7}を考える．ある 1

on Computing, vol. 11(4):721-736, 1982.

点を o，2 つの正の実数をC, 3とし，E, :, <, Kは5% (C )上に，この順序で並べ，点 e は:7 = <K = 23となるような4% (C)内に配置する．このような 5 点の組を(@, C, 3)と表記することとする．ここで，このような点配置は準一般的配置ではないが，微小に配置を動かすことで準一般的配置にすることとする．

=を正の整数として，(@, C, 3)の組を t 倍することを考える．E, :, <, K, 7の; 番目のものをそれぞれE& , :& , <& , K& , 7& とする（図 6(b)）．このとき，以下の定理が成り立つ．
定理 4. 任意の] > 0についてN(/) ≥ (1.25 − ])|/|を満たす準一般的配置の点集合/が存在する．
5. 今後の課題

01!(/)の双対グラフを考えた際，その双対グラフに閉

報告 H109－ 562 －