On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs
Preprint
Abstract
Several types of linear layouts of graphs are obtained by leveraging known data structures; the most notable representatives are the stack and the queue layouts. In this content, given a data structure, one seeks to specify an order of the vertices of the graph and a partition of its edges into pages, such that the endpoints of the edges assigned to each page can be processed by the given data structure in the underlying order. In this paper, we study deque and rique layouts of graphs obtained by leveraging the double-ended queue and the restricted-input double-ended queue (or deque and rique, for short), respectively. Hence, they generalize both the stack and the queue layouts. We focus on complete and complete bipartite graphs and present bounds on their deque- and rique-numbers, that is, on the minimum number of pages needed by any of these two types of linear layouts.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The mixed page number of graphsTheoretical Computer Science, 2022
- Stack-Number is Not Bounded by Queue-NumberCombinatorica, 2021
- Planar graphs that need four pagesJournal of Combinatorial Theory, Series B, 2020
- The pagenumber of k-trees is O(k)Discrete Applied Mathematics, 2001
- On the Pagenumber of Complete Bipartite GraphsJournal of Combinatorial Theory, Series B, 1997
- Laying Out Graphs Using QueuesSIAM Journal on Computing, 1992
- Comparing Queues and Stacks As Machines for Laying Out GraphsSIAM Journal on Discrete Mathematics, 1992
- Embedding planar graphs in four pagesJournal of Computer and System Sciences, 1989
- Pagenumber of complete bipartite graphsJournal of Graph Theory, 1988
- The book thickness of a graphJournal of Combinatorial Theory, Series B, 1979