Cliques in hyperbolic and weighted geometric graphs

• Applicant: Professor Dr. Thomas Bläsius
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 524989715

The core difference between theory and practice in the area of algorithmics is that theoretical analysis typically aims to obtain guarantees that hold for any input, while actual implementations are evaluated on practical instances. We aim to narrow this gap by theoretically studying input models that resemble practical data from various domains regarding important structural properties. This lets us study the algorithmic implications of these properties in an idealized setting, which then feeds back into the development of practically efficient algorithms. The scope of this project is the study of cliques in graphs with underlying geometry. To allow for heterogeneous degree distributions, we consider hyperbolic geometry and, alternatively, weighted points and distances. Besides structural insights on cliques, we want to study the algorithmic implications of these insights. Moreover, we plan to evaluate the capability of our input models to represent practical inputs. At its core, we aim to answer the following three questions: What is the clique structure in graphs with underlying hyperbolic and weighted geometry? What are the algorithmic implications of this clique structure? How well do our findings in these idealized models translate to real-world inputs?

• DFG Programme: Research Grants