Topological Stack-Queue Mixed Layouts of Graphs

Miki MIYAUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.2   pp.510-522
Publication Date: 2020/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019EAP1097
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
graph layout,  number of subdivisions of graphs,  stack layout of graphs,  queue layout of graphs,  stack-queue mixed layout of graphs,  

Full Text: PDF(856.7KB)>>
Buy this Article




Summary: 
One goal in stack-queue mixed layouts of a graph subdivision is to obtain a layout with minimum number of subdivision vertices per edge when the number of stacks and queues are given. Dujmović and Wood showed that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(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 subdivision layout with at most 2⌈logs+q-1sn(G)⌉ (resp. at most 2⌈logs+q-1qn(G)⌉ +4) division vertices per edge. That is, this paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results.