Date: Tue, 30 Nov 2010 14:43:27 +0100 (CET)
From: arrangementer@diku.dk
Subject: Talk by Arash Farzan at DIKU

Speaker: Arash Farzan from Max-Planck Institute for Informatics, Saarbrucken, 
Germany. 

Arash is working in the Algorithms and Complexity group 
at MPII. His main research area is Data Structures.
Arash is visiting University of Copenhagen (DIKU) for this week.

Subject: Algorithms and Data Structures

Time: Friday, 3 December 2010 at 11:00–11:30
Place: Meeting Room A+B at DIKU

Title: Succinct Representation of Separable Graphs

Abstract:

We consider the problem of highly compact encoding of separable graphs.
Separable graphs are those that admit an O(nc)-separator theorem where
c < 1.  Our encoding supports navigation queries in constant time in the
RAM with logarithmic word size. Namely, we show adjacency, degree, and
neighborhood queries are supported in constant time.
For any monotone class of separable graphs, the storage requirement of the
encoding matches the information-theory minimum to within lower order 
terms.

Many graphs in computational geometry that arise in practice are indeed
separable. In particular, planar graphs are separable, and therefore, we
achieve the first such succinct encoding for planar graphs.
We also show how the scheme can be adapted to succinctly encode the
combinatorial embedding of planar graphs (and hence encode planar maps).