抄録A-007
Stack-queue mixed layouts of graph subdivisions
Stack-queue mixed layouts of graph subdivisions
○宮内美樹（NTT）・榎本彦衛（早大）
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}.
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}.
