WEKO3
アイテム
A-001 内部3連結グラフの外6角格子凸描画(A分野:モデル・アルゴリズム・プログラミング,一般論文)
https://ipsj.ixsq.nii.ac.jp/records/151975
https://ipsj.ixsq.nii.ac.jp/records/15197577242284-567a-462a-b85a-83fa54fb4184
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00009336258.pdf (145.6 kB)
|
Copyright (c) 2013 by IEICE,IPSJ
|
| Item type | FIT(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-08-20 | |||||||
| タイトル | ||||||||
| タイトル | A-001 内部3連結グラフの外6角格子凸描画(A分野:モデル・アルゴリズム・プログラミング,一般論文) | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A-001 Outer Hexagonal Convex Grid Drawings of Internally Triconnected Plane Graphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 福島大学理工学群共生システム理工学類 | ||||||||
| 著者名 |
三浦, 一之
× 三浦, 一之
|
|||||||
| 著者名(英) |
Miura, Kazuyuki
× Miura, Kazuyuki
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 平面グラフGの凸描画においては,全ての辺は交差しない直線分で描かれ,全ての面は凸多角形で描かれる.Gの凸描画で,各点が整数座標を持ち,外面がk角形であるものを外k角格子凸描画という.Gが凸描画を持つための必要十分条件は,Gが内部3連結であることである.nをGの点数としよう.Gが3連結であるか,あるいはGの3連結成分分解木T(G)の葉の数が3枚以下ならば,Gは大きさn×nの整数格子内に外3角格子凸描画できる.また,T(G)の葉の数がちょうど4枚ならば大きさ2n×2nの整数格子内に外4角格子凸描画できる.更に,T(G)の葉の数がちょうど5枚ならば大きさ6n×n^2の整数格子内に外5角格子凸描画できる.本論文では,T(G)の葉が6枚のとき,内部3連結グラフGは6n×n^2の大きさの整数格子内に外6角格子凸描画できることを証明すると共に,そのような描画を求める線形時間アルゴリズムを与える. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA1242354X | |||||||
| 書誌情報 |
情報科学技術フォーラム講演論文集 巻 12, 号 1, p. 127-128, 発行日 2013-08-20 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
