Geometric Networks

Organizers: Jit Bose, Mark de Berg, and Matya Katz

Content workshop:

Networks (road networks, energy networks, communication networks, social networks) form the backbone of our society. In many cases these networks are geometric: the nodes and edges are embedded in the plane or in some higher-dimensional space. In the proposed workshop we will focus on two aspects of geometric networks.

  • Stochastic / probabilistic aspects of geometric networks. Stochasticity plays an important role in real-life networks, in the processes that take place on the networks and/or in the processes that generate the networks. The first part of the workshop focuses on these aspects. Topics of interest include random graphs, graph structures on random point sets, geometric networks where edges may fail.
  • Applied aspects of geometric networks, in particular sensor networks. The second part of the workshop focuses on algorithmic and combinatorial problems on sensor networks. Topics may include questions on unit-disk graphs, conflict-free colorings, routing strategies, and so on.


The 4th Annual Minisymposium on Computational Topology

Organizers: Brittany Terese Fasy, Elizabeth Munch, and Don Sheehy

Content workshop:

The application of topological techniques to traditional data analysis has led to a boost in the research area of computational topology. Past years have witnessed a large and ever-growing range of applications and connections with other mathematical disciplines. At the same time, computational topology is closely connected to discrete and computational geometry, reflected by the fact that CG week is the major annual conference for both fields simultaneously.

This mini-symposium has two major goals: On the one hand, we want to illuminate how computational geometry and topology fertilize each other, by surveying recent advances on the interface of both areas. On the other hand, we cover two recent trends in topology that connect the field to statistical data analysis and to categorical algebra.

This minisymposium will be composed of three workshops:

  1. From Computational Geometry to Topology
    Organized by Ulrich Bauer, Michael Kerber, and Don Sheehy
  2. Statistical Approaches to Topological Data Analysis
    Organized by Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasserman
  3. Sheaves and Categories
    Organized by Vin de Silva and Elizabeth Munch


Stochastic Geometry and Random Generation

Organizers: Olivier Devillers and Xavier Goaoc

Content workshop:

Probabilistic methods are ubiquitous in computer science and computational geometry is no exception: from randomized algorithms, average-case complexity analysis of algorithms, to Erdós' probabilistic lens in discrete geometry, probabilistic methods have had a major impact on the field.

Most often, probabilistic methods are used in computational geometry by computational geometers themselves. There are, however, entire areas dedicated to the understanding of the properties of random geometric objects (stochastic geometry) or random generation mechanisms (analytic combinatorics).

The proposed workshop aims at stimulating new interactions between these areas and the international community of discrete and computational geometers.


Geometric Intersection Graphs: Problems and Directions

Organizers: Piotr Micek and Bartosz Walczak

Content workshop:

Graphs represented by geometric objects have been studied in computational geometry from the very beginning, because of various practical applications as well as the beautiful combinatorics they give rise to. In recent years, a lot of progress has been made in the study of geometric intersection graphs. In this workshop, we would like to survey major open problems concerning various aspects of geometric intersection graphs, discuss promising approaches to them, and propose some directions for further research. The following topics are likely to be covered:

  • computational complexity of recognition and partial representation extension,
  • approximation algorithms for the maximum clique and maximum independent set problems,
  • separators in geometric intersection graphs,
  • colorings of geometric intersection graphs with bounded clique number,
  • extremal problems on geometric and topological graphs
    (in particular, the k-quasi-planar graph conjecture).