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.
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Programa Estatal de I+D+i Orientada a los Retos de la Sociedad
Retos de Investigación: Proyectos de I+D+i
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco
Arseneva, E.; Bose, P.; Cano, M.; D'Angelo, A.; Dujmovic, V.; Frati, F.; Langerman, S.; Tappini, A. International Symposium on Graph Drawing and Network Visualization p. 371-384 DOI: 10.1007/978-3-030-04414-5_27 Presentation's date: 2018-09-18 Presentation of work at congresses
Fabila, R.; Hidalgo, C.; Huemer, C.; Lara, D.; Mitsche, D. International Symposium on Graph Drawing and Network Visualization p. 593-605 DOI: 10.1007/978-3-030-04414-5_42 Presentation's date: 2018 Presentation of work at congresses