The search functionality is under construction.
The search functionality is under construction.

Topological Stack-Queue Mixed Layouts of Graphs

Miki MIYAUCHI

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.2 pp.510-522
Publication Date
2020/02/01
Publicized
Online ISSN
1745-1337
DOI
10.1587/transfun.2019EAP1097
Type of Manuscript
PAPER
Category
Graphs and Networks

Authors

Miki MIYAUCHI
  NTT Corporation

Keyword