Reyan Ahmed

Research interest: Graph Algorithms, Network Visualization, Data Science

Projects:

• Graph spanners: A spanner is a subgraph that preserves the shortest path distances approximately. Real-life networks contain millions of nodes, billions of edges, and an algorithm will be computationally expensive if the network is dense. In that case, we can compute a spanner to generate a sparse graph but with similar properties. Note that, Steiner tree is a special case of spanners. We formulated a multi-level version of spanners and a weighted version of additive spanners. We developed efficient algorithms for different types of spanners.
• Network visualization using maps: Maps are used in day to day life for visualizing geographic maps e.g. Google Maps. There is a relationship between networks and maps: any planar graph can be converted to a map and vice versa. However, even if the graph is not planar a similar idea can be applied. A network can capture multi-relational data and have a significant impact on data visualization. The goal of this project is to visualize large networks using maps that incorporate semantic zooming as other traditional maps. We are using this visualization currently on research networks.
• 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 kind of neural network called 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.

Journal Publications:

• Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-level Steiner trees, J. Exp. Algorithmics, 2019.
• Reyan Ahmed, Md. Saidur Rahman, Stephen Kobourov, Online facility assignment, Theoretical Computer Science, 2019, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2019.08.011.

Conference Publications:

• Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence. On additive spanners in weighted graphs with local error, In Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, (also arXiv:2103.09731), 2021.
• Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Multi-level Weighted Additive Spanners, In Proceedings of the 20th International Symposium on Experimental Algorithms (also arXiv:2102.05831), 2021.
• Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, and Mingwei Li. Graph Drawing via Gradient Descent, (GD)², arXiv:2008.05584, In Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020). (best paper award)
• Reyan Ahmed, Greg Bodwin, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Weighted Additive Spanners, In Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, (also arXiv:2002.07152), 2020.
• Reyan Ahmed, Keaton Hamm, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Kruskal-based approximation algorithm for the multi-level Steiner tree problem, In Proceedings of the 28th Annual European Symposium on Algorithms, (also arXiv:2002.06421), 2020.
• Sabin Devkota, Reyan Ahmed, Felice De Luca, Kate Isaacs, Stephen Kobourov. Stress-Plus-X (SPX) Graph Layout, arXiv:1908.01769, In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
• Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Approximation algorithms and an integer program for multi-level graph spanners, In Proceedings of the 18th International Symposium on Experimental Algorithms (also arXiv:1904.01135), 2019.
• Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-level steiner trees, In Proceedings of 17th International Symposium on Experimental Algorithms, pages 15:1-15:14 (also arXiv:1804.02627), 2018.
• Reyan Ahmed, Md. Saidur Rahman and Stephen Kobourov, Online Facility Assignment, In Proceedings of 12th International Workshop on Algorithms and Computation, pages 156-168, 2018. (best paper award)
• Reyan Ahmed, Md. Mazharul Islam and Md. Saidur Rahman, On acyclic colorings of graphs. In Proceedings of 15th International Conference on Computer and Information Technology (ICCIT 2012), pages 95-100, 2012.

Other Publications:

• Kathryn Gray, Mingwei Li, Reyan Ahmed, Stephen Kobourov. Visualizing Evolving Trees, arXiv:2106.08843, 2021.
• Kathryn Gray, Mingwei Li, Reyan Ahmed, Md. Khaledur Rahman, Ariful Azad, Stephen Kobourov, Katy Börner. Scalable Methods for Readable Tree Layouts, Submitted to HICSS (available in https://tiga1231.github.io/zmlt/demo/doc/paper.pdf), 2021.
• Saad Al Muttakee, Reyan Ahmed, and Md. Saidur Rahman. New Results and Bounds on Online Facility Assignment Problem, arXiv:2009.01446, 2020.
• Reyan Ahmed, Greg Bodwin, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Graph Spanners: A Tutorial Review, Computer Science Review, 37, p.100253 (also arXiv:1909.03152), 2020.
• Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Multi-Level Graph Sketches via Single-Level Solvers, arXiv:1905.00536, 2019.
• Reyan Ahmed, Felice De Luca, Sabin Devkota, Alon Efrat, Md Iqbal Hossain, Stephen Kobourov, Jixian Li, Sammi Abida Salma and Eric Welch, L-Graphs and Monotone L-Graphs, 1703.01544, 2017.

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: 13 Oak Drive Hamilton, NY 13346, Colgate University.
• Phone: +1 520 247 7268.