Plane Drawings of Queue and Deque Graphs

Auer, Christopher and Bachmaier, Christian and Brandenburg, Franz J. and Brunner, Wolfgang and Gleißner, Andreas (2011) Plane Drawings of Queue and Deque Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 68-79(Official URL:

Full text not available from this repository.


In stack and queue layouts the vertices of a graph are linearly ordered from left to right, where each edge corresponds to an item and the left and right end vertex of each edge represents the addition and removal of the item to the used data structure. A graph admitting a stack or queue layout is a stack or queue graph, respectively. Typical stack and queue layouts are rainbows and twists visualizing the LIFO and FIFO principles, respectively. However, in such visualizations, twists cause many crossings, which make the drawings incomprehensible. We introduce linear cylindric layouts as a visualization technique for queue and deque (double-ended queue) graphs. It provides new insights into the characteristics of these fundamental data structures and extends to the visualization of mixed layouts with stacks and queues. Our main result states that a graph is a deque graph if and only if it has a plane linear cylindric drawing.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_7
Classifications: P Styles > P.999 Others

Actions (login required)

View Item View Item