The EuroGIGA programme consists of four Collaborative Research Projects (CRPs):
GraDR: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
ComPoSe: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
VORONOI: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 ...
GReGAS: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
