BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Reyan Ahmed

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.CO

Catalog footprint

Research overview

5works
4topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

5 publications

preprint2022arXiv

An FPT Algorithm for Bipartite Vertex Splitting

Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as a 2-layered drawing, where each set of objects is visualized as a set of vertices (points) on one of the two parallel horizontal lines and the relationships are represented by edges (simple curves) between the two lines connecting the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings this, however, is computationally expensive and may still result in drawings with so many crossings that they affect the readability of the drawing. We consider a recent approach to remove crossings in such visualizations by splitting vertices, where the goal is to find the minimum number of vertices to be split to obtain a planar drawing. We show that determining whether a planar drawing exists after splitting at most kk vertices is fixed parameter tractable in kk.

Open access
preprint2022arXiv

Visualizing Evolving Trees

Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github.

Open access
preprint2020arXiv

Graph Drawing via Gradient Descent, (GD)2(GD)^2

Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, (GD)2(GD)^2, that can handle multiple readability criteria. (GD)2(GD)^2 can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of (GD)2(GD)^2 with experimental data and a functional prototype: \url{http://hdc.cs.arizona.edu/~mwli/graph-drawing/}.

Open access
preprint2020arXiv

Graph Spanners: A Tutorial Review

This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

Open access
preprint2020arXiv

Kruskal-based approximation algorithm for the multi-level Steiner tree problem

We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals TT require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals uu, vv with priorities P(u)P(u), P(v)P(v) are connected using edges of rate min⁡{P(u),P(v)}\min\{P(u),P(v)\} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio clog⁡log⁡nc \log \log n, where nn is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min⁡{2(ln⁡∣T∣+1),ℓρ}\min\{2(\ln |T|+1), \ell ρ\}-approximation in this setting, where ρρ is an approximation ratio for a heuristic solver for the Steiner tree problem and ℓ\ell is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39ρ\approx 1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal's minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.