Dear all, there may be a change of program for the colloquium. Our next and last Monday's Lecture and Colloquium will take
place on July 18 at 14:15 & 16:00 at FU Berlin. You are all cordially invited. Location: Freie Universität Berlin Takustr. 9 14195 Berlin Time: Monday, July 18  14:15 Lecture: Herman Haverkort (Universität Bonn) Title: Spacefilling curves: properties, applications and challenges Abstract:A spacefilling curve is a continuous, surjective map from [0,1] to a ddimensional unit volume (for example, a cube or a simplex). Spacefilling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in ddimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how spacefilling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal spacefilling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a spacefilling curve. Coffee & Tea Break : Room 134  1st Floor Time: Monday, July 18  16:00 s.t. Colloquium: Andrea Jiménez (Universidad de Varparaíso, Chile) Title: Grid subdivisions, wall minors and treewidth in planar graphs Abstract:Minors, subdivisions and treewidth are classical notions that appear for example in the seminal characterization of planar graphs by Kuratowski and in the celebrated Graph Minor Theorem by Robertson and Seymour. The importance of grid/wall minors comes from one of the results of Robertson and Seymour, which roughly claims that a graph of large treewidth necessarily contains a large grid/wall minor. The concept of treewidth is fundamental in algorithmic graph theory since many problems which are hard to solve in general, can be efficiently solved when restricted to classes of graphs with bounded treewidth. In this talk, we discuss the computational complexity of the
Minor Problem, the Subdivision Problem and the
Treewidth Problem with input: grids/walls and planar graphs.
Surprisingly, some of these problems are still open. We describe
two reductions which prove that the respective GridSubdivision
Problem and the WallMinor Problem are NPcomplete problems.
