## Speaker:

Franz Brandenburg - Faculty of Informatics, University of Passau

## Title:

Stacks, Queues and Deques and their Representation as Graphs

## Location:

Archway 2 - 1:00 pm, Friday 16 March

## Abstract:

Stacks and queues are fundamental data structures. They express the LIFO
(last-in, first out) and FIFO (first-in, first-out) principles and are the basis
for depth first and breadth first search. Stacks and queues are a specialization
of a deque, which allows the insertion and removal of objects on its left and
right ends. In Java 6 the class Arraydeque implements a deque and is likely to
be faster than Stack when used as a stack, and faster than LinkedList when used
as a queue.

We consider classes of graphs which represent the input-ouput behaviour of these
data structures, and call them stack, queue, or deque graphs. Then the
input-output actions on a stack are correct if and only if the stack graph is
planar. Accordingly, queue graphs have a planar representation on a cylinder and
the deque graphs are characterized by planar graphs on the cylinder with
additional arches.

We study properties of the classes of stack, queue and deque graphs, which are
subclasses of planar graphs. In particular, one stack graphs are two queue
graphs, and one queue graphs are two stack graphs. Our latest result states that
in terms of graphs a deque dominates two stacks exactly by the difference
between a Hamilton cycle and a Hamilton path in planar graphs.
These representation of graph can also be used to display permutations
as graphs.

## Bio:

Franz J. Brandenburg received his PhD from the University of Bonn in 1978, and
his habilitation in 1982. Since 1983 he is a full professor of Informatics at
the University of Passau.

His research interest is in computational complexity,
algorithmics, and particularly in graph drawing. One of the earliest graph
drawing tool (Graphed) was developed in his group; follow-ups are Graphlet and
Gravisto. Current reserach projects are on drawing graphs on surfaces, such as
cylinders and tori, drawings with data structures, and ranking problems with
incomplete information.

He is one of the founding members of the International Symposium on Graph
Drawing. He was chairman and dean of the Faculty of Informatics in Passau
and President of the German Computer Science Faculties Association.