| No | 200426 |
|---|---|
| 標題（和） | 単色辺からなるグラフのトラックレイアウト |
| 標題（英） | Track layout of bipartite graph with single-color edges |
| 研究会名（和） | 信号処理, 回路とシステム, 通信方式 |
| 研究会名（英） | Signal Processing, Circuits and Systems, Communication Systems |
| 開催年月日 | 2010-03-01 |
| 終了年月日 | 2010-03-02 |
| 会議種別コード | 5 |
| 共催団体名（和） | |
| 資料番号 | CAS2009-91, SIP2009-136, CS2009-86 |
| 抄録（和） | グラフの細分のトラックイアウトについては，DujmovicとWoodによって，任意のグラフGにたいし，各辺が8logd qn(G) +1個の細分点を持つGの細分の(d+2)-トラックレイアウトが存在することが示された．本論文では２部グラフに対してこの結果を改良し，m頂点，n頂点(m≥n)からなる部集合を持つ任意の2部グラフGm,nに対して，各辺が 4logd n個の細分点を持つGm,n の細分の(d+2)-トラックレイアウトが存在することを示す． |
| 抄録（英） | This paper studies the problem of track layout of bipartite graph subdivisions. Dujmovic and Wood showed that every graph G has a (d+2)-track subdivision with 8logd qn(G) +1 division vertices per edge. This paper improves this result for the case of bipartite graphs Gm,n (m≥n) with m and n partite sets, and shows that for every integer d ≥2, every bipartite graph Gm,n (m≥n) has a (d+2)-track subdivision with 4 logd n division vertices per edge. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.109, No.434,435,436 |
| ページ開始 | 75 |
| ページ終了 | 80 |
| キーワード（和） | グラフドローイング,2部グラフ,グラフの細分,グラフのトラックレイアウト |
| キーワード（英） | graph drawing,bipartite graph,subdivision,track layout of graphs |
| 本文の言語 | JPN |
| 著者（和） | 宮内美樹 |
| 著者（ヨミ） | ミヤウチ ミキ |
| 著者（英） | Miki Miyauchi |
| 所属機関（和） | 日本電信電話株式会社NTTコミュニケーション科学基盤研究所 |
| 所属機関（英） | NTT Communication Science Laboratories, NTT Corporation |