Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 15, 2012, 12:15 pm
Duration: 30 minutes
Location: HG D5.2
Speaker: Ueli Peter
A class of graphs is separable if it is closed under the subgraph relation and if every member with n vertices has a separator of size O(nc) for some c < 1. In in this talk we discuss a data structure by Blandford, Blelloch and Kash which is able to store separable graphs using O(n) bits. This generalizes a result by Turan which states that planar graphs can be stored using O(n) bits.
Automatic MiSe System Software Version 1.4803M | admin login