[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium July 18. Program.

[Ita Brunke <i.brunke@fu-berlin.de>]

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:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 18 - 14:15

Lecture: Herman Haverkort (Universität Bonn)

Title: Space-filling curves: properties, applications and challenges

Abstract:

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling 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 d-dimensional 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 space-filling 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 space-filling 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 space-filling 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 NP-complete problems.

This is joint work with Tina Janne Schmidt and with Carla Lintzmayer and Maycon Sambinelli.