The restricted input queue (rique) is a data structure which is recently introduced to study linear layout of graphs. The rique data structure is a special queue where insertions occur only at the head and removals occur at both the head and the tail. Considering a rique data structure the goal of a linear layout of a graph is to find a linear order of the vertices of the graph and a partition of its edges into pages such that the edges in each page follow the restriction of rique in the underlying order. The rique number of a graph is the smallest number of pages required for linear layout of the graph with rique data structure. A characterization of graphs for admitting a single page rique layout and some bounds on the rique number of complete and complete bipartite graphs are known. In this paper, we show that the rique number of series-parallel graphs as well as planar bipartite graphs is 2.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Rique Number of Series-Parallel Graphs and Planar Bipartite Graphs

  • Sk Ruhul Azgor,
  • Md. Saidur Rahman

摘要

The restricted input queue (rique) is a data structure which is recently introduced to study linear layout of graphs. The rique data structure is a special queue where insertions occur only at the head and removals occur at both the head and the tail. Considering a rique data structure the goal of a linear layout of a graph is to find a linear order of the vertices of the graph and a partition of its edges into pages such that the edges in each page follow the restriction of rique in the underlying order. The rique number of a graph is the smallest number of pages required for linear layout of the graph with rique data structure. A characterization of graphs for admitting a single page rique layout and some bounds on the rique number of complete and complete bipartite graphs are known. In this paper, we show that the rique number of series-parallel graphs as well as planar bipartite graphs is 2.