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.