平面グラフの直線分描画の高さについて

概要

論文の詳細を見る
グラフの各枝を互いに交差しない曲線によって平面に描いた図形を平面グラフと呼ぶ.平面グラフの各枝がすべて直線分によって描かれているとき,特にこれを直線分描画と呼ぶ.計算機で直線分描画を処理したり,ディスプレイに出力する場合は,描画されたグラフの点には整数値のxy座標が与えられる.このような直線分描画は格子上にある,あるいは格子上の直線分描画であるという.格子上の直線分描画に関する問題の一つに,「任意のn点の平面グラフを格子上の直線分描画するために十分な領域はどのくらいか」というものがある.この問いに対する答えとして,現在までの最良の結果は「任意のn点の平面グラフは幅n-2,高さn-2の領域内で格子上に直線分描画できる」というものであるが,これらの値が必要十分であるかどうかはわかっていない.筆者はこうした結果を踏まえ,高さ(もしくは幅)のみについてであれば,必要十分な値を求められる-任意のn点の平面グラフを格子上に直線分描画するために必要十分な高さは⌈(2n-4)/3⌉-と予想する.本文では,この予想を裏付ける結果として,任意のn点の平面グラフGは,点のy座標のうち互いに異なるものが高々⌈(2n-1)/3⌉個であるような直線分描画G^*を持つことを構成的に示す.
一般社団法人情報処理学会の論文
1993-09-15

平面グラフの直線分描画の高さについて

スポンサーリンク

概要

著者

関連論文

スポンサーリンク