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

Miki MIYAUCHI

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 G_m,n has a (d+1,2)-track layout of a subdivision of G_m,n with 2 log _d n -1 division vertices per edge, where m and n are numbers of vertices of the partite sets of G_m,n with m ≥ n.

• Publication: IEICE TRANSACTIONS on Fundamentals 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
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Authors

Miki MIYAUCHI

Keyword

graph drawing,  graph layout,  bipartite graph,  subdivision,  track,  track layout