グラフの辺が本の背と ⌈m log_d n⌉ の交差数をもつd+1ページ本型への埋蔵
スポンサーリンク
概要
- 論文の詳細を見る
グラフの本型埋め込みとは、各頂点は本の背上にあり、各辺は本のページ上にどの任意の辺同士も共通の頂点以外ではお互いに交差しないように埋め込まれた埋め込みのことである。従来のグラフの本型埋め込みでは辺は頂点以外では本の背との交差を許していないが、ここでは辺は背をまたがって複数ページに埋蔵可能であるという条件のもとでの考察をおこなう。このとき任意のグラフに対し、3ページあれば必ず本型埋め込みが可能であることが既に知られている。以前に著者らは、頂点数n辺数mのグラフに対し本の背とグラフの辺との交差数がO(m log n)となるような3ページへの埋蔵方法を示した。本結果はオーダに関しては最善であることも得られている. 本論文ではこの埋蔵方法を改良して交差数を減らし、任意のグラフに対して本の背とグラフの辺との交差数が ⌈m log_d n⌉ となるような3ページへの本型埋め込みを示した. 本結果はグラフの辺数が頂点数の2乗オーダの場合には係数に関して最善だと予想している.
- 一般社団法人情報処理学会の論文
- 1996-05-29
著者
関連論文
- 情報処理専門教育について 大学等における情報系専門教育の改善への提言
- グラフの辺が本の背と ⌈m log_d n⌉ の交差数をもつd+1ページ本型への埋蔵
- グラフの辺が本の背とO(m log_dn)の交差数をもつd+1ページ本型への埋蔵
- グラフの本型埋め込みアルゴリズムについて
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (信号処理)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (通信方式)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (回路とシステム)
- 単純無向グラフ自動描画アルゴリズム ( 情報の可視化)