内部3連結平面グラフの
格子凸描画
西関研究室 7650 橋本友也
格子凸描画
平面グラフ
•すべての辺が交差しないように直線分
で描画
•すべての点が整数格子点上に存在
格子描画
格子凸描画
格子凸描画
凸
凸
平面グラフ
•すべての辺が交差しないように直線分
で描画
•すべての点が整数格子点上に存在
•すべての面が凸多角形
格子凸描画
凸
凸描画の方が見やすいことが多い
格子凸描画
格子凸描画
格子描画の面積
13×12=156
12
平面グラフ
•すべての辺が交差しないように直線分
で描画
•すべての点が整数格子点上に存在
•すべての面が凸多角形
格子凸描画
13
面積の小さな描画
が求められる
3連結成分分解木
内部3連結平面グラフ
凸描画できる
3連結成分分解木
3連結成分分解木
分離点対
内部3連結平面グラフではす
べての分離点対は外周上に
存在
3連結成分分解木
グラフを分離
仮想辺
分離点対がなくなるまで繰り返す
3連結成分分解木
3連結成分
3連結成分分解木
◦ 各節点が3連結成分に対応
◦ 共通の分離点対をもつ3連結成
分の間を辺で結ぶ
3連結成分分解木
既知の結果
分解木の
葉の枚数
3枚以下
4枚
5枚以上
内部3連結
平面グラフ
格子描画
の面積
Open problem
[CK97]、[MAN05]
n：グラフの点数
[ZN10]
に改良
アルゴリズム
a1
s2
s3
a2
s4
s5
s2
a1
s3
a2
s4
s1
s5
s8
a4
s7
s6
si:分離点対
n：Gの点数
a3
s1
s8
a4
s7
s6 a3
の分割
分割
a1
s2
s3
a1
a2
s2
s3
s4
s4
s1
s5
s1
s5
s8
a2
s8
分割
a4
s7
n：Gの点数
s6
a3
a4
s7
a3
s6
nu：Guの点数
nd：Gdの点数
a1
nu
a2
nu
a1
s2
s3
s5
a2
s4
s5
s1
s8
a4
の傾きは-45゜, 0゜or [45゜,90゜]
s7
s6
nu：Guの点数
nd：Gdの点数
[CK97]、
[MAN05]の
3角形描画
a3
s1
nd
a4
nd
a3
a1
nu
a2
nu
傾き＞1のとき
s5
s1
nd
a4
nd
a3
a1
αu
nu
a2
nu
傾き＞1のとき
s5
傾き=1
s1
nd
a4
nd
αd
a3
a1
αu
nu
a2
nu
傾き＞1のとき
s5
αu ≦nu
αd ≦nd
2nu
2nd
s1
nd
a4
nd
αd
a3
シフト法
αu
nu
a1
a2
nu
a1
s2
s3
s5
a2
2nu
s4
s5
s1
2nd
s8
a4
s7
s6
nu：Guの点数
nd：Gdの点数
[CK97]、
[MAN05]の
3角形描画
a3
s1
nd
a4
nd
αd
a3
a1
max{2nu, 2nd}= 2nd<2n
a2
nu
a1
s2
s3
s5
a2
2nu
s4
s5
s1
2nd
s8
a4
s7
s6
nu：Guの点数
nd：Gdの点数
[CK97]、
[MAN05]の
3角形描画
a3
s1
nd
a4
nd
αd
a3
a1
|傾き|≦1のとき
max{2nu, 2nd}= 2nd<2n
a2
nu
s5
max{nu, nd}
|傾き|＞1
s1
nd
a4
nd
αd
a3
a1
max{2nu, 2nd}= 2nd<2n
a2
nu
s5
W ＝ max{2nu, 2nd} ＜ 2n
H ＝ nu + nd + max{nu, nd}
＝ (nu + nd) + nd
max{nu, nd}
＜ 2n
時間計算量：線形時間
|傾き|＞1
s1
nd
a4
nd
αd
a3
まとめ
分解木の
葉の枚数
3枚以下
4枚
5枚以上
内部3連結
平面グラフ
格子描画
の面積
Open problem
[CK97]、[MAN05]
n：グラフの点数
[ZN10]
既知の結果
まとめ
分解木の
葉の枚数
3枚以下
4枚
5枚以上
内部3連結
平面グラフ
格子描画
の面積
Open problem
[CK97]、[MAN05]
n：グラフの点数
本研究の結果
今後の課題
Thanks!
補足スライド
従来
改良点
本研究
の傾きは-45゜, 0゜or 45゜
の傾きは-45゜, 0゜or [45゜,90゜]
2nd
nd
nd
2nd
改良点
傾き＞1のとき
本研究
の傾きは-45゜, 0゜or [45゜,90゜]
nd
nd
従来
改良点
本研究
の傾きは-45゜, 0゜or 45゜
の傾きは-45゜, 0゜or 45゜
2nd
nd
2nd
2nd
従来
改良点
本研究
2nd
nd
2nd
2nd
既知の結果
平面グラフ
2連結平面グラフ
分離点対
内点
凸描画できない
既知の結果
平面グラフ
2連結平面グラフ
分離点対
内点
凸描画できない
既知の結果
平面グラフ
2連結平面グラフ
分離点対
内点
凸描画できない
既知の結果
平面グラフ
2連結平面グラフ
内部3連結平面グラフ
2連結グラフの任意の分離点対{u,v}について
– {u,v}がともに外点
– G－{u,v}の各連結成分が外点をもつ
既知の結果
平面グラフ
2連結平面グラフ
内部3連結平面グラフ
u
v
凸描画できる
© Copyright 2024 ExpyDoc
