On the Rique Number of Series-Parallel Graphs and Planar Bipartite Graphs
摘要
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.