Reyan Ahmed

Research interest: Graph Algorithms, Network Visualization, Data Science

Projects:

• Graph spanners: Graph spanners are subgraphs that approximate the shortest path distances of the original graph while significantly reducing its density. Real-world networks often consist of millions of nodes and billions of edges, making computations on dense graphs highly expensive. Spanners help address this issue by constructing sparse subgraphs that retain essential structural properties. A Steiner tree is a special case of a spanner. Our research focuses on developing efficient algorithms for various types of spanners, including single-level weighted additive spanners and multi-level spanners. The goal of this spanner construction is to facilitate the visualization of large-scale networks. Similar to an interactive geographic map—where continents appear at the highest level, followed by countries, highways, and streets as we zoom in—our approach aims to represent networks in a hierarchical manner. At the top level, the most important nodes and connections are visible, and as we zoom in, additional details, such as intermediate nodes that link higher-importance nodes, gradually emerge.
• Network visualization using maps: We are developing scalable and readable visualizations for large-scale networks using multi-level spanners and efficient layout algorithms. While spanners help reduce complexity, we are ensuring that a well-structured layout makes the visualization clearer. Force-directed algorithms create natural layouts but often introduce edge crossings and label overlaps, which we are addressing. Inspired by the four-color theorem, we are using clustering techniques to transform networks into intuitive, map-like representations. We are designing a tree layout algorithm that prevents edge crossings, avoids label overlaps, preserves edge lengths, and maintains compactness. Extending this approach to general graphs, we extract hierarchical structures and integrate spanner-based techniques. This enables seamless, multi-level exploration, making complex networks more interpretable.
• Solving graph problems using GNN: Neural networks are one of the most popular tools in data science. A traditional neural network is sequential and does not work well for multi-relational objects like graphs. A special type of neural network called a Graph Neural Network (GNN) has been developed to handle such objects. GNNs have shown promising results for NP-complete problems. We are working on different models of GNNs to solve graph-related problems. Currently, we are using GNNs to compute Steiner trees.
• Graph drawing via gradient descent: Developing an optimization framework that simultaneously optimizes stress together with several other criteria: edge crossings, minimum crossing angle, and upwardness (for directed acyclic graphs). This is a machine learning approach for network visualization. We are using different variations of gradient descent to generate layouts that optimize multiple criteria at the same time. The algorithms designed to optimize one criterion only typically do not provide good results on other metrics, whereas our approach has the flexibility to optimize multiple criteria as well as preserving the network topology.
• Online facility assignment: We formulated an online problem where a set of facilities is situated on an object e.g. graph, plane, line. Each facility has a capacity. The customers appear in an online manner and have to be assigned to a free facility before a new customer appears. We developed different deterministic and randomized algorithms for this problem. This problem is related to game theory, the analysis of the algorithms we are developing is similar to a game between an online player and an adversary.

Presentations:

• Conference presentation in the 20th International Symposium on Experimental Algorithms 2021 (virtual conference). Topic: Multi-level Weighted Additive Spanners. (Slides)
• Conference presentation in the 28th International Symposium on Graph Drawing and Network Visualization 2020 (virtual conference). Topic: Graph Drawing via Gradient Descent, (GD)². (Slides, Movie)
• Conference presentation in the 28th Annual European Symposium on Algorithms, 2020 (virtual conference). Topic: Kruskal-based approximation algorithm for the multi-level Steiner tree problem. (Slides, Movie)
• Conference presentation in the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, 2020 (virtual conference). Topic: Weighted additive spanners. (Slides, Movie)
• Invited speaker in the SIAM student seminar, the department of mathematics, the University of Arizona, 2020 (virtual presentation). Topic: Multi-level Graph Spanners.
• Poster presentation in TRIPODS conference, 2019. Topic: Approximation algorithms and an integer program for multi-level graph spanners.
• Conference presentation in the 12th International Workshop on Algorithms and Computation, 2018. Topic: Online facility assignment.

Contact:

• Address: GS 831, The University of Arizona, AZ 85721, USA.
• Phone: +1 520 247 7268.