| 講演名 | 2004-06-25 本型空間への2部グラフの埋蔵 宮内 美樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフの本型空間への埋め込みとは,各頂点は本の背上にあり,各辺は本のページ上にどの任意の辺同士も共通の頂点以外ではお互いに交差しないように埋め込まれた埋め込みのことである.ここでは辺は背をまたがって複数ページに埋蔵可能であるという条件のもとでの考察をおこなう.このとき任意のグラフに対し,3ページあれば必ず本型埋め込みが可能であることが既に知られている.以前に,頂点数n,辺数mの一般のグラフに対し本の背とグラフの辺との交差数がO(m log_dn)となるようなd+1ページヘの埋蔵方法を示した.さらに本結果はオーダに関しては最善であることも示した.本論文ではそれぞれm頂点と,n頂点(m>n)からなる2個の部分グラフを持つ2部グラフG_ |
| 抄録(英) | 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_dn) times. This result is the best possible for K_n in this case. This paper shows that there exists a d+1-page book embedding of a bipartite graph G_ |
| キーワード(和) | 2部グラフ / 本型埋め込み / 本の背と辺との交差数 |
| キーワード(英) | Bipartite graph / Book embedding / Crossings of edges over the spine |
| 資料番号 | COMP2004-24 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 本型空間への2部グラフの埋蔵 |
| サブタイトル（和） | |
| タイトル（英） | Embedding bipartite graphs into book space |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 2部グラフ / Bipartite graph |
| キーワード(2)（和/英） | 本型埋め込み / Book embedding |
| キーワード(3)（和/英） | 本の背と辺との交差数 / Crossings of edges over the spine |
| 第 1 著者 氏名（和/英） | 宮内 美樹 / Miki MIYAUCHI |
| 第 1 著者 所属（和/英） | NTTコミュニケーション科学基礎研究所 NTT Communication Science Laboratories |
| 発表年月日 | 2004-06-25 |
| 資料番号 | COMP2004-24 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 147 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |