For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Queue Layout of Bipartite Graph Subdivisions
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/05/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
graph drawing, graph layout, bipartite graph, subdivision, queue, queue layout,
Full Text: PDF>>
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).