WEKO3
アイテム
平面グラフの直線分描画の高さについて
http://hdl.handle.net/10191/8946
http://hdl.handle.net/10191/89468724f245-89bb-4ee3-9da1-094dcd274299
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
34(9)_1853-1858.pdf (510.5 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2009-07-15 | |||||
| タイトル | ||||||
| タイトル | 平面グラフの直線分描画の高さについて | |||||
| タイトル | ||||||
| タイトル | 平面グラフの直線分描画の高さについて | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| その他のタイトル | ||||||
| その他のタイトル | On Heights of Straight Line Drawings of Plane Graphs | |||||
| 著者 |
高橋, 俊彦
× 高橋, 俊彦 |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 40435 | |||||
| 姓名 | Takahashi, Toshihiko | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | グラフの各枝を互いに交差しない曲線によって平面に描いた図形を平面グラフと呼ぶ．平面グラフの各枝がすべて直線分によって描かれているとき，特にこれを直線分描画と呼ぶ．計算機で直線分描画を処理したり，ディスプレイに出力する場合は，描画されたグラフの点には整数値のxy座標が与えられる．このような直線分描画は格子上にある，あるいは格子上の直線分描画であるという．格子上の直線分描画に関する問題の一つに，「任意のn点の平面グラフを格子上の直線分描画するために十分な領域はどのくらいか」というものがある．この問いに対する答えとして，現在までの最良の結果は「任意のn点の平面グラフは幅n-2，高さn-2の領域内で格子上に直線分描画できる」というものであるが，これらの値が必要十分であるかどうかはわかっていない．筆者はこうした結果を踏まえ，高さ（もしくは幅）のみについてであれば，必要十分な値を求められる-任意のn点の平面グラフを格子上に直線分描画するために必要十分な高さは⌈(2n-4)/3⌉-と予想する．本文では，この予想を裏付ける結果として，任意のn点の平面グラフGは，点のy座標のうち互いに異なるものが高々⌈(2n-1)/3⌉個であるような直線分描画G^*を持つことを構成的に示す． | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | Let G^* be a straight line drawing of a plane graph in the xy-plane. The number of y-coordinates (of vertices) d(G^*) is the number of vertices with pairwise distinct y-coordinates in G^*. d(G^*) is a parameter which is closely related to the height of straight line drawing of a graph on a grid. We show that any plane with n vertices has a drawing which satisfies d(G^*) ≤⌈(2n-1)/3⌉ and present a constructive algorithm which obtains such a straight line drawing. | |||||
| 書誌情報 |
情報処理学会論文誌 en : 情報処理学会論文誌 巻 34, 号 9, p. 1853-1858, 発行日 1993-09 |
|||||
| 出版者 | ||||||
| 出版者 | 情報処理学会 | |||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 03875806 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00116647 | |||||
| 著者版フラグ | ||||||
| 値 | publisher | |||||
