グラフの辺が本の背とO(m log_dn)の交差数をもつd+1ページ本型への埋蔵
スポンサーリンク
概要
- 論文の詳細を見る
本論文では、グラフの本型埋め込みの問題について研究する。グラフの本型埋め込みとは、各頂点は本の背上にあり、各辺は本のページ上にどの任意の辺同士も共通の頂点以外ではお互いに交差しないように埋め込まれた埋め込みのことである。著者は以前に、頂点数n辺数mのグラフに対し、本の背とグラフの辺との交差数がO(m log_2n)となるような3ページの本型への埋め込み方法と、n頂点完全グラフK_nの本型埋め込みの際生じる交差数はΩ(n^2)となることを証明した。本論文では、任意の頂点数n辺数mのグラフを本の背とグラフの辺との交差数がO(m log_dn)になるようなd+1ページの本型への理め込みが存在すること、また完全グラフK_nのd+1ページへの本型埋め込みの際に生じる交差数の下限を検討する。
- 社団法人電子情報通信学会の論文
- 1995-05-26
著者
関連論文
- グラフの辺が本の背と ⌈m log_d n⌉ の交差数をもつd+1ページ本型への埋蔵
- グラフの辺が本の背とO(m log_dn)の交差数をもつd+1ページ本型への埋蔵
- グラフの本型埋め込みアルゴリズムについて
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (信号処理)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (通信方式)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (回路とシステム)