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

概要

論文の詳細を見る
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[logdqn(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[logdn]-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n with m≥n.
The Institute of Electronics, Information and Communication Engineersの論文
2008-09-01