Go to the content (press return)

Geometry and graphs: interactions and applications

Total activity: 15
Type of activity
Competitive project
Funding entity
Funding entity code
136.730,00 €
Start date
End date
algoritmos geométricos, combinatorial geometry, computational geometry, geometric algorithms, geometric graphs (theory and applications), geometría combinatoria, geometría computacional, grafos geométricos (teoría y aplicaciones)
The unifying focus of this project is computational geometry, with emphasis on both combinatorial and algorithmic problems on the
relationship between combinatorial graphs and their geometric embeddings. This disciplinary framework is inserted into a wider one,
namely discrete and algorithmic mathematics. Its major development in recent times is due to its association with computer and
communication technologies. This is why it still requires an intense and sustained research effort.
With this project we want to channel the general research activity of the group, with its multiplicity of cooperative working lines, while at the
same time intensifying work on a specific topic: the interaction between combinatorial and geometric graphs. Simultaneously, we intend to
consolidate the direction initiated in the previous project (MTM2012-30951/FEDER) intensifying the identification and study of problems
arising from application areas. Although one cannot ignore the fact that our research is of theoretical kind, we cannot ignore either that
many of the problems that computational geometry studies arise from its many applications.
We have structured our proposal in three lines of work of a fundamental nature:
A1. Domination in combinatorial graphs,
A2. Domination and coverings in geometric graphs,
A3. Geometric embedding of combinatorial graphs,
plus another two, more oriented towards applications:
B1. Modular robotic system reconfiguration,
B2. Geometric algorithms for geographic information,
Regarding the foundations of theoretical type, the research lines we propose seek to delve into the study of combinatorial properties of
graphs (A1) whose transposition to geometric graphs (A2) is of great interest for the research community in combinatorial and algorithmic
geometry: domination, location, covering... This relationship between properties of combinatorial graphs and those of geometric graphs is
also evident in the crucial fact that is reflected in A3: on the one hand, the study of combinatorial properties of graphs is eased by the study
of their embeddings in the plane and, conversely, the study of sets of points -in the plane and in higher dimension- is eased by studying
the graphs they determine. As for the applications, the three subjects that this project aims to emphasize are linked to the previous
subjects because the algorithms of B1 rely on properties of regular graphs and minimum spanning trees, and some of the problems of B2
are directly related to visibility problems on terrains.
Main objective: scientific achievements. The natural objective of this project is to obtain as complete and advanced results as possible in
the study of the algorithmic-geometric problems described above.
Additional objectives: in parallel with the main objective, we have two other complementary goals which are also natural in a project of this
nature: maintaining the international projection of the group, and maintaining our efforts into training young researchers.
Adm. Estat
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Call year
Funcding program
Programa Estatal de I+D+i Orientada a los Retos de la Sociedad
Funding call
Retos de Investigación: Proyectos de I+D+i
Grant institution
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco


Scientific and technological production

1 to 15 of 15 results