| 大会名称 |
|---|
| 2016年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2016 |
| 発行日 |
| 2016-08-23 |
| セッション番号 |
| 1A |
| セッション名 |
| アルゴリズム（１） |
| 講演日 |
| 2016/09/07 |
| 講演場所(会議室等) |
| 共通教育棟E棟2階E23 |
| 講演番号 |
| A-003 |
| タイトル |
| 3連結cubic平面グラフの最少線分格子凸描画 |
| 著者名 |
| 三浦一之, |
| キーワード |
| アルゴリズム, グラフ理論, 凸描画, 最少線分格子凸描画 |
| 抄録 |
|
平面グラフGの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．Gの凸描画で，各点が整数座標を持つものを格子凸描画という．Gの凸描画で，極大線分の数が最少となるものを最少線分凸描画という．Gの最少線分凸描画で，各頂点が整数格子上にあるものを最少線分格子凸描画という．Gが3連結cubicグラフならば，Gは最小線分凸描画を持つことが知られている．更に，Gが3連結cubicグラフならば，Gは大きさ(n/2+1)x(n/2+1)の整数格子内に，極大線分の数が下限より高々1本多い格子凸描画を持つことが知られている．ここで，nはGの点数を表す． 本論文では，Gが3連結cubicグラフならば，Gは大きさ(3n/2+1)x(5n/2+1)の整数格子内に最少線分格子凸描画できることを証明するとともに，そのような描画を求める線形時間アルゴリズムを与える． |
| 本文pdf |
| PDF download (162KB) |