講演抄録/キーワード |
講演名 |
2004-06-25 15:20
本型空間への2部グラフの埋蔵 ○宮内美樹(NTT) |
抄録 |
(和) |
グラフの本型空間への埋め込みとは,各頂点は本の背上にあり,各辺は本のページ上にどの任意の辺同士も共通の頂点以外ではお互いに交差しないように埋め込まれた埋め込みのことである.ここでは辺は背をまたがって複数ページに埋蔵可能であるという条件のもとでの考察をおこなう.このとき任意のグラフに対し,3ページあれば必ず本型埋め込みが可能であることが既に知られている.以前に,頂点数n,辺数mの一般のグラフに対し本の背とグラフの辺との交差数がO(m log_d n)となるようなd+1ページへの埋蔵方法を示した.さらに本結果はオーダに関しては最善であることも示した.本論文ではそれぞれn_1頂点とn_2頂点(n_1> n_2)からなる2個の部分グラフを持つ2部グラフG_{n_1,n_2}に対して検討をし,この埋蔵方法を改良して交差数を減らし,任意の2部グラフG_{n_1,n_2}に対して,本の背とグラフの各辺との交差数がlog_d n_2となるようなd+1ページへの本型埋め込みを示した.本結果は最高次数の係数に関して最善だと予想している. |
(英) |
This paper studies the problem of book-embeddings of bipartite graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, we have shown that there exists a d+1-page book embedding of G in which each edge crosses the spine O(log_d n) times. This result is the best possible for Kn in this case. This paper shows that there exists a d+1-page book embedding of a bipartite graph G_{n_1,n_2} (n_1> n_2) in which each edge crosses the spine log_d n_2 times. We conjecture that our result is the best possible as to the coefficient of the highest degree. |
キーワード |
(和) |
2部グラフ / 本型埋め込み / 本の背と辺との交差数 / / / / / |
(英) |
Bipartite graph / Book embedding / Crossings of edges over the spine / / / / / |
文献情報 |
信学技報, vol. 104, no. 147, COMP2004-24, pp. 41-45, 2004年6月. |
資料番号 |
COMP2004-24 |
発行日 |
2004-06-18 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|