Graph Algorithms with Geometric Applications
Name of applicant
Eva Rotenberg
Institution
Technical University of Denmark
Amount
DKK 4,944,663
Year
2022
Type of grant
Semper Ardens: Accelerate
What?
Large networks appear numerous places in computer science and other sciences. Examples include social networks, transportation networks, 3D meshes, electric circuits, and many more. Large networks, as other big data, require efficient algorithms to compute answers to questions about their properties. In this project we will approach questions on the border between geometry and algorithms for large networks. On one hand, we will devise and implement new efficient algorithms that are tailored to work for networks that stem from spatially embedded data, such as 3D meshes. On the other hand, we will study fundamental questions about visualising large networks, and seek new efficient algorithms with provable mathematical guarantees for producing drawings with rigorously defined qualities.
Why?
1. Networks that stem from geometrically embedded shapes have special properties which are interesting to identify and exploit when creating efficient algorithms, and the related application areas such as computer graphics prompt interesting graph-algorithmic problems. 2. How to draw a graph or network under restrictions to the resulting drawing are fundamental questions, that draw upon insights from discrete mathematics, and have applications in network visualisation. Computing such drawings, or updating them to reflect changes in the network, are interesting areas with many unanswered questions.
How?
We aim to obtain results that range from mathematical theorems and proofs, through algorithms and data structures with provable mathematical guarantees, to thoroughly tested and documented publicly available programs. We hope to utilise the group’s expertise on practical and theoretical algorithms research towards an impact in relevant theoretical areas, and in actual practical applications, while exploiting synergies between related methods and topics.