Graphs in Geometry and Algorithms (EuroGIGA)

EuroGIGA is a collaborative research programme running from 2011 till 2014. It addresses the basic but difficult problems summarized under the name ’Graphs in Geometry and Algorithms’ by establishing a European-wide collaboration which unites efforts of researchers from the fields of Geometry, Graph Theory, and Computer Science. This joint effort has a mission to foster collaboration and cross-fertilization with application areas where geometric graphs and algorithms play a role, like combinatorial optimization, geographic information systems, computer-aided design, robotics, or image analysis, to name a few.

Background and objectives

Geometric graph and hypergraph structures are at the core of Discrete and Computational Geometry, and simultaneously, they are a crucial tool in applications. Many important problems can be formulated as problems on graphs that include geometric information or implicitly represent it. In particular, geometric graphs are of great importance in Computer Science. For example, in various problem settings, the output object is a geometric graph, possibly augmented with auxiliary combinatorial or geometric information. Estimating the size of the desired object to be calculated then just means giving upper and lower bounds on the storage requirement. Moreover, combinatorial arguments on geometric graphs frequently arise in the analysis of the runtime of algorithms. Since many seemingly unrelated problems have convenient geometric interpretations, the study of geometric graph structures touches upon, and sheds light into various classes of questions. Solutions to these questions find applications not only in many practically oriented areas of computer science, such as geographic information systems, computer graphics, robotics, and geometric modeling, but also in the applied sciences. Moreover, several problems formulated for geometric graphs belong to the list of prominent open problems in discrete mathematics. Solving such problems is not solely of theoretical interest but will influence future directions of research in the entire area of algorithmic and geometric graphs.

By coordinating the scattered efforts in the area of geometric graphs and algorithms, this EUROCORES Programme consolidates the existing and partially fragmentary knowledge on these structures that has accumulated so far. It brings together the most advanced techniques from algorithms, combinatorics, algebra, topology, and polyhedral geometry, as well as computer experiments to conquer new frontiers and eventually bring back the fruits of this research to (more applied) algorithmic analysis and to other branches of mathematics which are based on these fundamental questions, addressing the following research topics:

• Drawing graphs;

• Geometric representations of graphs;

• Skeletal structures and spatial  decompositions;

• Combinatorics of discrete point sets;

• Graphs of polytopal structures.