论文标题
图形编号
The Rique-Number of Graphs
论文作者
论文摘要
我们继续研究与已知数据结构有关的图形线性布局。在高水平上，给定数据结构，目标是找到图形顶点的线性顺序，并将其边缘的分区分成页面，以便每个页面中的边缘遵循基础顺序中给定数据结构的限制。在这方面，最著名的代表是堆栈和队列布局，同时还存在一些deques的工作。 在本文中，我们研究了遵循限制输入队列（Rique）的限制的图形线性布局，其中插入仅在头部出现，并且在头部和尾部都发生了去除。我们表征了使用单页的Rique布局的图表，并使用表征来得出相应的测试算法，当时输入图是最大平面。最终，我们对完整图的所需页面（所谓的Rique-number）数量进行了界限。
We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal 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 the given data structure in the underlying order. In this regard, the most notable representatives are the stack and queue layouts, while there exists some work also for deques. In this paper, we study linear layouts of graphs that follow the restriction of a restricted-input queue (rique), in which insertions occur only at the head, and removals occur both at the head and the tail. We characterize the graphs admitting rique layouts with a single page and we use the characterization to derive a corresponding testing algorithm when the input graph is maximal planar. We finally give bounds on the number of needed pages (so-called rique-number) of complete graphs.
