Discrete mathematics studies the mathematical properties of structures that can be accurately represented by a computer. It is omnipresent in everyday life: encryption techniques, for example when paying with a credit card or when surfing the Internet, are based on methods of discrete mathematics. Another example are optimization problems, for example when designing train timetables or when planning industrial supply chains. More generally, discrete mathematics forms the theoretical backbone of computer science - an understanding of how an algorithm works is impossible without mathematics.
The consortium of our doc.fund brings together colleagues from TU Graz and the University of Graz and focuses on building bridges between sub-areas of discrete mathematics. Our consortium emerges from the doctoral program “Discrete Mathematics”, which was financially supported by the FWF from 2010 to 2024 and has firmly anchored research in this area in Graz and made it internationally visible. We concentrate on fundamental research without losing sight of application areas. We define the term discrete mathematics broadly, extending into the areas of number theory, algebra and theoretical computer science, and thus cover a wide range of research fields. The specific topics in the doc.funds project range from the question of which polynomials can be represented as a sum of squares, to computability in networks with limited information, to the problem of which surfaces can be made from textile material.
Each doctoral position in this doc.funds project is supervised equally by two members of the consortium. In most cases, the support takes place at different institutes and the proposed projects lie at the intersection of their expertise. This means we work on innovative and highly relevant research topics with optimal team support. In addition, we are continuing our proven tools for excellent doctoral training, for example our lively weekly seminar, the opportunity for long-term stays at foreign research institutions, and a successful mentoring program. This results in excellent training, both for an academic career and for many sectors of the economy. In fact, graduates of our predecessor program hold responsible positions in a wide variety of areas, such as consulting, software development, insurance and data analysis.
- Österreichischer Wissenschaftsfonds FWF, FWF
- Amt der Steiermärkischen Landesregierung, Abteilung Wirtschaft, Tourismus, Wissenschaft und Forschung, Zukunftsfonds Steiermark - Geschäftsstelle, A12
- Universität Graz, Institut für Mathematik und Wissenschaftliches Rechnen
Beginn: 30.09.2024
Ende: 29.09.2028
Arrangements of geometric objects and drawings of graphs lie at the core of modern Discrete and Computational Geometry. They serve as a exible tool in applications in both mathematics
and computer science, since many important problems that involve geometric information may be modeled as problems on arrangements or graphs. Therefore, the study of these structures and a better understanding of their properties impacts a wide variety of problem domains. This DACH project \Arrangements and Drawings" connects groups that have already cooperated successfully in the European collaborative research programme EuroGIGA. In this follow-up project, we plan to investigate the relationships between different types of drawings and arrangements, as well as their abstract representations and their algorithmic properties. We have
composed a list of challenging problems from the following four focus areas: (A) Arrangements of lines and pseudolines, (B) Drawings of graphs, (C) Structure of intersection, and (D) Planar and near-planar structures.
The goal of this project is to gain insights in order to broaden our understanding of these areas and to jointly attack some of their long-standing open questions. These questions are
notoriously diffcult though important, so that even partial solutions are expected to have impact.
- Österreichischer Wissenschaftsfonds FWF, FWF
- Eidgenössische Technische Hochschule Zürich, ETH
- Technische Universität Berlin, Institut für Mathematik
- Freie Universität Berlin
Beginn: 26.08.2018
Ende: 25.08.2021
The general topic of this project is the investigation of geometric
graphs, i.e., graphs where the vertex set is a point set in the
plane and the edges are straight line segments spanned by these points.
Throughout we assume the points to be in general position, that is no
three of them lie on a common line, and to be labeled.
Geometric graphs are a versatile data structure, as they include
triangulations, Euclidean spanning trees, spanning paths,
polygonalizations, plane perfect matchings and so on. The
investigation of geometric graphs belongs to the field of
(combinatorial) mathematics, graph theory, as well as to discrete and
computational geometry. The alliance of our two research groups will
perfectly cover these fields. For example this will allow us to use
an interesting combination of enumerative investigations (lead by the
Austrian team) and theoretical research (coordinated by the Spanish
group). Let us point out that this combination of theoretical
knowledge and practical experience, which is perfectly provided by the
combination of these two teams, will be essential for the success of
this project.
There are many classic as well as new tantalizing problems on
geometric graphs, and the investigation of seemingly unrelated
questions often leads to new relations and deeper structural insight.
So the focus of this project is to investigate several classes of
problems with the common goal of optimizing properties of geometric graphs.
- Österreichischer Austauschdienst GmbH - Agentur für Internationale Bildungs- und Wissenschaftskooperation, OeAD
- Universidad de Alcalá, E.T.S.I. Informática
Beginn: 31.12.2007
Ende: 30.12.2009
Zentrales Thema dieser gemeinsamen Forschung ist die Untersuchung
grundlegender Datenstrukturen aus dem Bereich der rechnerischen
Geometrie (Computational Geometry), einem relativ jungen Teilgebiet
der (theoretischen) Informatik. Dabei sollen sowohl theoretische
Aspekte untersucht werden, als auch deren konkrete Umsetzung im Rahmen
einer allgemein verwendbaren Programmbibliothek.
Auf Seite der theoretischen Untersuchungen sollen sowohl klassische
Datenstrukturen, wie Voronoi-Diagramme oder Triangulierungen, aber auch
relativ neue Datenstrukturen, wie Pseudo-Triangulierungen oder
Straight-Skeletons, untersucht werden. Genauere Einzelheiten werden in
den nachfolgenden Abschnitten beschrieben. Gleichzeitig soll aber auch
für alle untersuchten Strukturen deren tatsächliche
Verwendbarkeit in der Praxis berücksichtigt werden. So ist es
geplant, jeweils spezielle Aspekte dieser Strukturen in konkreten
Implementationen umzusetzen. Um einen bestmöglichen Nutzen der
erzielten Ergebnisse zu gewährleisten, sollen die Implementationen
in einer standardisierten Bibliothek der gesamten CG-Community zur
Verfügung gestellt werden. Dazu ist die Umsetzung in CGAL
(Computational Geometry Algorithms Library, siehe { www.cgal.org})
geplant. Es handelt sich dabei um ein ursprünglich von
der EU gefördertes Projekt, das insbesondere von unserem
französichen Projektpartner an zentraler Stelle mitbetrieben wird.
- Österreichischer Austauschdienst GmbH - Agentur für Internationale Bildungs- und Wissenschaftskooperation, OeAD
- National Institute for Research on Computer Science and Control, Unité de recherche INRIA Sophia-Antipolis
Beginn: 31.12.2006
Ende: 30.12.2008
Computational Geometry is dedicated to the algorithmic study of elementary geometric questions. Traditionally it deals with basic geometric objects like points, lines, and planes. For real world applications, however, often reliable techniques for advanced geometric primitives like surfaces and location query structures are needed.
The role of this project is twofold. On one hand it will provide the theoretical background for advanced geometric algorithms and data structures for several other projects within this joint research project (JRP). These include geometric structures for fast information retrieval, the generation and manipulation of triangular meshes, the computation of suitable distance functions to multidimensional objects, and the representation of advanced geometric objects.
Another aim of this project is to develop novel techniques for the manipulation and optimization of geometric structures. Here the emphasis is on geometric graphs (triangulation-like and Voronoi diagram-like structures, spanning trees). Properties of these structures will be investigated, with the goal of designing more efficient geometric algorithms and data structures.
Existing geometric algorithms libraries (CGAL, LEDA) will be used to guarantee robustness of the developed algorithms.
- Österreichischer Wissenschaftsfonds FWF, FWF
- Johannes Kepler Universität Linz, Institut für Angewandte Geometrie
- Leopold-Franzens-Universität Innsbruck, Fakultät für Mathematik, Informatik und Physik, Institut für Informatik
- Technische Universität Wien, Geometric Modeling and Industrial Geometry
Beginn: 31.03.2005
Ende: 30.12.2011