Graphs can be used as effective models in a very diverse range of domains, within and without computer science. When used as such, they form an appealing and intuitive abstraction in which only the essentials of the domain are represented. Based on graph models, their analysis, their transformation and their evolution over time, understanding of and predictions about the systems being modelled ensue.
The topic of graphs leads to projects of varying nature, ranging from theoretical (the study of graph properties and the mechanics of graph transformation) and application-oriented (developing graph-based models for a particular domain, be it chemical, physical, or digital) to implementation (designing and implementing particular analyses or search strategies).
Related Courses
- Graph Transformations (202100114)
- Graph Algorithms and Complexity (201900082)
- Graph Theory (191520751)
Available Project Proposals
If you are interested in the general topic of Graphs, or if you have your own project idea related to the topic, please contact us directly. Alternatively, you can also work on one of the following concrete project proposals:
Complexity metrics on graph models Supervisor: Milan Lopuhaä-Zwakenberg
Graphs are an essential tool for modeling high-tech systems. The complexity of a graph can be measured in many ways, from simple metrics like the number of nodes and edges, to more complicated ones such as algebraic connectivity and treewidth. The goal of this project is to study which complexity metrics are relevant in modeling: What do measure, and how easy are they to compute? And does a metric actually tell us what we want to know?
Although no company is involved, it is possible to devote (part of) the project to a case study such as Facebook or the Dutch railway system.
Supervisor: Faizan Ahmed
If you have your own proposal related to algorithms for hypergraphs you can contact me. A possible example is approximation algorithms for maximal cliques in hypergraphs.
Heuristics for graph problems Supervisor: Milan Lopuhaä-Zwakenberg and Yanni Dong
If you have your own proposal related to heuristics for graph problems, please contact me to discuss the opportunities. The general approach is to study an NP-hard graph problem of your choice and develop heuristics for finding good solutions.
Contact
