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).