抄録

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}.