For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovi and D. R. Wood showed that for every integer d ≥ 2, every graph G has a d-queue layout of a subdivision of G with 2logd qn(G)+1 division vertices per edge, where qn(G) is the queue number of G. This paper improves the result for the case of a bipartite graph, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a d-queue layout of a subdivision of Gm,n with logd n-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n (m ≥ n).

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine log n times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine logd n times.

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine logd n times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph Gn1,n2 having two partite sets with n1 and n2 vertices respectively (n1 ≥ n2) in which each edge crosses the spine logd n2 -1 times.

A (k,2)-track layout of a graph G consists of a 2-track assignment of G and an edge k-coloring of G with no monochromatic X-crossing. This paper studies the problem of (k,2)-track layout of bipartite graph subdivisions. Recently V. Dujmovi and D.R. Wood showed that for every integer d ≥ 2, every graph G with n vertices has a (d+1,2)-track layout of a subdivision of G with 4 log d qn(G) +3 division vertices per edge, where qn(G) is the queue number of G. This paper improves their result for the case of bipartite graphs, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a (d+1,2)-track layout of a subdivision of Gm,n with 2 log d n -1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n with m ≥ n.

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.