EuroGIGA Collaborative Research Projects


Graph Drawings and Representations

Click here to visit GraDR pages ...

GraDR Summary:

The main goal of this CRP is to foster collaborative research in the areas of graph drawing and geometric representations of graphs, and by coordinating and unifying the efforts of top European research groups to attack basic and notoriously difficult open problems in the area. Incorporating young researchers and students in the research teams and organizing tutorials and schools for them will help transfer our know-how to the next generation. At the same time we will make efforts to implement our theoretical findings in graph drawing and visualization toolkits and other applications that are being developed by member teams of the CRP.

Individual projects:

Jan Kratochvil, Charles University, Praha, Czech Republic
Slope number; crossing Number

Stefan Felsner, Technische Universität Berlin, Germany
Angular schematization; contact and intersection representations; transfer to practice; hypergraphs with applications and bioinformatics

Michael Hoffmann, ETH Zürich, Switzerland
Simultaneous embeddings

János Pach, Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Quasi- and near-planar graphs

Jaroslaw Grytczuk, Jagiellonian University, Kraków, Poland
Coloring graphs with geometric representations

Associate partners:

Giuseppe Di Battista, Universita Roma Tre, Italy
Clustered planarity

Bettina Speckmann, Technische Universiteit Eindhoven, Netherlands
Region constrained graph drawing

Dorothea Wagner, University of Karlsruhe, Germany
Constrained embeddings

Top of page ...


Combinatorics of point sets and Arrangements of Objects

Click here to visit ComPoSe pages ...

ComPoSe Summary:

This CRP focuses on combinatorial properties of discrete sets of points and other simple geometric objects primarily in the plane. In general, geometric graphs are a central topic in discrete and computational geometry, and many important questions in mathematics and computer science can be formulated as problems on geometric graphs. We will, among others, investigate Erdös-Szekeres-type problems, questions on colored point sets, and problems on counting, enumerating and sampling of crossing-free configurations. It is the vision of the members of this CRP to make a massive joint effort in order to gain deeper insight into the structure of long-standing problems in the field, and to contribute major steps towards their final solution.

Individual projects:

Oswin Aichholzer, Graz University of Technology, Austria
Erdos-Szekeres type problems for colored point sets and compatible graphs

Jean Cardinal, Université Libre de Bruxelles, Belgium
Coloring Arrangements of Geometric Objects

Stefan Felsner, Technische Universität Berlin, Germany
Arrangements and Higher Dimensions

Fernando Alfredo Hurtado Díaz, Universitat Politècnica de Catalunya, Barcelona, Spain
Point sets and graphs: geometric bridges

Pavel Valtr, Charles University, Prague, Czech Republic
Geometric and topological graphs, and Erd}os-type problems

Emo Welzl, ETH Zürich, Switzerland
Crossing-Free Con gurations in the Plane | Counting, Enumeration,and Sampling

Associate partners:

János Pach, Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Structural Properties of Arrangements of Convex Bodies

Top of page ...


Spatial Decompositions and Graphs

Click here to visit VORONOI pages ...

VORONOI Summary:

Many theoretical and practical geometric problems lead to decompositions of space as part of their analysis or as part of their solution: The Voronoi diagram and its dual decomposition, the Delaunay tessellation is just the most classical and fundamental example. The underlying "space" can be the Euclidean ambient space that we live in, or some more abstract parameter space or for example the configuration space of a robot. On the one hand, there are many hard questions about the classical Voronoi diagrams that remain open (such as complexity of Voronoi diagrams of moving points). On the other hand, many spatial decompositions that can be considered as variations of Voronoi diagrams have recently emerged, for example decompositions defined by some converging process such as Newton's method for finding roots, or decompositions that are related to pattern matching problems. For these new structures, even some basic questions (like uniqueness, the basic structure of cells) have not been investigated. Four main structures will be investigated: (i) Voronoi diagrams, (ii) Skeletal structures, (iii) Variants of triangulations, and (iv) Proximity graphs.

Individual projects:

Günter Rote, Freie Universität Berlin, Germany
Voronoi Diagrams for Shape Matching

Franz Aurenhammer, Technische Universität Graz, Austria
Advanced Voronoi and Delaunay Structures

Bert Jüttler, Johannes Kepler University, Linz, Austria
Medial Axis Computation

Rolf Klein, University of Bonn, Germany
Abstract Voronoi Diagrams and Region Areas

Miroslaw Kowaluk, Warsaw University, Poland
Neighborhood Graphs for Large Point Sets

Evanthia Papadopoulou, Università della Svizzera Italiana, Lugano, Switzerland
Hausdor and Higher-Order Voronoi Diagrams

Alberto Márquez, Universidad de Sevilla, Spain
Voronoi Diagrams for Vision Angles; Triangulations and Quadrangulations with Structural Constraints

Assoicate partners:

Stefan Langerman, Université Libre de Bruxelles, Belgium
Geometric Spanner Graphs and Geometric Networks

Top of page ...


Geometric representations and symmetries of graphs, maps and other discrete structures and applications in science

Click here to visit GReGAS pages ...

GReGAS Summary:

Geometric and other representations of graphs and graph based combinatorial structures have important applications in mathematics, computer science, social networks, chemistry, bioinformatics, etc. The main goal of the project is to develop a coherent theory of graph representations with emphasis on symmetric and near symmetric structures or products. The research will be followed by applications of the acquired knowledge to geometrically rich combinatorial structures like configurations, maps and polytopes, as well as to usually less symmetric large networks. The motivation for research will arise mainly from applications in mathematical chemistry, bioinformatics and social networks. The project consists of five themes:

  • Representations and structure of graphs and other discrete structures: Development of coherent representation theory by integrating the results of research.
  • Near symmetric structures or products. Representations related to graph products using (algebraic) structures that give rise to highly regular and/or symmetric families of graphs.
  • Representations of symmetric graphs. Use of symmetries of highly symmetric graph for obtaining graph representations.
  • Representations of configurations, maps and polytopes. Structural properties of configurations, maps and polytopes are studied through symmetries with a goal of finding relevant geometrical representations for combinatorial structures.
  • Representations of large networks and applications in chemistry, bioinformatics and social networks: Applications of representation theory and algorithms in other disciplines especially in large networks.

Individual projects:

Tomaž Pisanski, University of Ljubljana, Slovenia
Graph representations, configurations and maps

Vladimir Batagelj, University of Ljubljana, Slovenia
Large networks

Türker Biyikoglu, Isik University, Istanbul, Turkey
Spectral Methods

Sandi Klavžar, University of Ljubljana, Slovenia
Isometric Embeddings into Product-Like Graphs

Antoaneta Klobucar, University J.J.Strossmayer, Osijek, Croatia
Some Applications of the Geometric Representations of Graphs

Dragan Marušič, Natural Sciences and Information Technologies University of Primorska, Koper, Slovenia
Representations of symmetric graphs

Martin Škoviera, Comenius University, Bratislava, Slovak Republic
Maps, Symmetries, Configurations and Colourings

Peter F. Stadler, University of Leipzig, Germany
Graphs in Molecular Biology

Associate partners:

Dimitri Leemans, Université Libre de Bruxelles, Belgium
Maps, polytopes and configurations

Josef Leydold, University of Economics and Business, Vienna, Austria
Near Graph Products

Leah Berman, University of Alaska Fairbanks, United States
Representations of configurations

Marston Conder, University of Auckland, New Zealand
Structural properties of graphs and maps

Patrick Fowler, University of Sheffield, United Kingdom
Graphs and graph representations in chemistry & molecular physics

Wilfried Imrich, Montanuniversitaet Leoben, Leoben, Austria
Near Products

Mikhail Klin, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Geometric methods in algebraic graph theory

Egon Schulte, Northeastern University, Boston, United States
Discrete structures in geometry

Top of page ...