Descripción
|
|
---|---|
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. In the current context, several families of geometric graphs, such as proximity and skeletal structures, constitute useful abstractions for the study of combinatorial properties of the point sets on which they are defined. For arrangements of other objects, such as lines or convex sets, their combinatorial properties are usually also described via an underlying graph structure. The following four tasks are well-known hard problems in this area and will form the backbone of the current project. We will consider the intriguing class of Erd?s-Szekeres type problems, variants of graph problems with colored vertices, counting and enumeration problems for specific classes of geometric graphs, and generalizations of order types as a versatile tool to investigate the combinatorics of point sets. All these problems are combinatorial problems on geometric graphs and are interrelated in the sense that approaches developed for one of them will also be useful for the others. Moreover, progress in one direction might provide a better understanding for related questions. Our main objective is to gain deeper insight into the structure of this type of problems and to contribute major steps towards their final solution. | |
Internacional
|
Si |
Tipo de proyecto
|
Proyectos y convenios en convocatorias públicas competitivas |
Entidad financiadora
|
European Science Foundation, MICINN |
Nacionalidad Entidad
|
ESPAÑA |
Tamaño de la entidad
|
Gran Empresa (>250) |
Fecha concesión
|
15/10/2011 |