| 大会名称 |
|---|
| 2014年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2014 |
| 発行日 |
| 2014/8/19 |
| セッション番号 |
| 5A |
| セッション名 |
| アルゴリズム基礎（１） |
| 講演日 |
| 2014/9/4 |
| 講演場所(会議室等) |
| 3B棟4F 3B405 |
| 講演番号 |
| A-007 |
| タイトル |
| Stack-queue mixed layouts of graph subdivisions |
| 著者名 |
| Hikoe Enomoto, Miki Miyauchi, |
| キーワード |
| graph layout, number of subdivisions of graphs, stack layout of graphs, queue layout of graphs, stack-queue mixed layout of graphs |
| 抄録 |
|
This paper studies the problem of stack-queue mixed layouts of graph subdivisions. Dujmovi'c and Wood showed that for every integer s,q>0, every graph G has an s-stack q-queue mixed subdivision layout with 4log_{(s+q)q} sn(G) (resp. 2+4log_{(s+q)q} qn(G)) division vertices per edge, where sn(G) (resp. qn(G)) is the stack number (resp. queue number) of G. This paper improves these results by showing that for every integer s,q>0, every graph G has an s-stack q-queue mixed subdivision layout with 2log_{alpha} sn(G)+2(resp. 2log_{alpha} qn(G)+4) division vertices per edge, where alpha is a function of s and q satisfying alpha > sqrt{(s+q)q}. |
| 本文pdf |
| PDF download (175.5KB) |