グラフのキューレイアウトの改良

摘要

2部グラフの細分のキューレイアウトについては，以前に著者が，m頂点，n頂点（m＞n）からなる2個の部集合を持つ任意の2部グラフG_(m,n)に対して，各辺が「log_2n」-1個の細分点を持つG_(m,n)の細分の2-キューレイアウトが存在することを示した．本論文では，その構成方法を改良する．%This paper studies the problem of queue layout of bipartite graph subdivisions. A 2-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into 2 sets of non-nested edges with respect to the vertex ordering. Previously, author showed that every bipartite graph G_(m,n)(m> n) has a 2-queue subdivision with 「log_2 n」 -1 division vertices per edge. This paper simplifies the way of construction of the result.