(d+1,2)-Track Layout of Bipartite Graph Subdivisions

Miki MIYAUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.9   pp.2292-2295
Publication Date: 2008/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.9.2292
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph drawing,  graph layout,  bipartite graph,  subdivision,  track,  track layout,  

Full Text: PDF>>
Buy this Article




Summary: 
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 mn.