Data Structures and their Planar Graph Layouts

Abstract

In a stack layout, also known as book embedding, the vertices of a graph are placed on a line and an edge is a data item that is pushed on the stack at the left vertex and removed at the right vertex. The LIFO principle of the stack is represented by a rainbow of nesting edges. We introduce linear cylindric drawings for the representation of the working principles of fundamental data structures including stack, queue, double-stack and deque. The resulting graphs are called stack (queue, double-stack, deque) graphs. We characterize the feasibility of a sequence of insertions and removals by planarity and use the graph classes to compare the relative power of these data structures. In particular, we show that the deque graphs are the linear cylindric planar graphs and are the subgraphs of the planar graphs with a Hamiltonian path. In comparison, the double-stack graphs are the graphs with a linear layout in the plane and are known as the subgraphs of the planar graphs with a Hamiltonian cycle. Hence, the power of the queue mode of a deque is expressed both by the differences between Hamiltonian path and Hamiltonian cycle and by linear layouts on the cylinder and in the plane. It is also reflected in the dual graph. Linear cylindric drawings provide an intuitive planar representation of the FIFO principle of a queue. We show that a queue graph augmented by a Hamiltonian path has a dual of the same type and that the dual has an Eulerian path. Finally, we study recognition problems.